# Bogo Sort

Source: https://wisconsin.twango.dev/fa24-cs300/u3-algorithms/sorting-and-search/sorting/bogo-sort

# Bogo Sort

> [!warning] Disclaimer
> Bogo sort is not within scope of COMP SCI 300, but was brought up in lecture for fun.

Bogo sort is a highly inefficient sorting algorithm that is not suitable for real-world use. It is a joke algorithm that is used to demonstrate the concept of sorting algorithms. The algorithm works by shuffling the array randomly and checking if it is sorted. If it is not sorted, it shuffles the array again and repeats the process until the array is sorted.

## Features

- [ ] Stable sorting algorithm
- [x] In-place sorting algorithm

## Implementation

### Pseudocode

```text
procedure bogoSort(A : list of sortable items)
    while not isSorted(A) do
        shuffle(A)
    end while
end procedure
```

### Java

```java
public static void bogoSort(int[] arr) {
    while (!isSorted(arr)) {
        shuffle(arr);
    }
}

public static boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
}

public static void shuffle(int[] arr) {
    Random rand = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = rand.nextInt(i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```

## Runtime Analysis

The time complexity of bogo sort is highly variable and depends on the number of elements in the array and the number of possible permutations. The worst-case time complexity is unbounded, as the algorithm may never sort the array. The average-case time complexity is $O(N \times N!)$, where $N$ is the number of elements in the array. This makes bogo sort extremely inefficient and impractical for sorting large arrays.

### Best Case

The best-case time complexity of bogo sort is $\Omega(N)$, which occurs when the array is already sorted. In this case, the algorithm will make a single pass through the array and return immediately.

### Worst Case

The worst-case time complexity of bogo sort is unbounded, as the algorithm may never sort the array. Therefore, the worst-case time complexity is $O(\infty)$.


## Source

The existing course note was retained and normalized during the merge.

Related: [[u3-algorithms/sorting-and-search/index|Topic index]].