Here is the pseudocode of the algorithm:
while not is_sorted(array)array := random_permutation(array)
This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n × n!). The exact expected running time depends on how many different element values occur, and how often each of them occurs, but for non-trivial cases the expected running time is exponential or super-exponential in n.
It should be noted that with real-world pseudo-random number algorithms, which have a finite number of states, the algorithm may never terminate for certain inputs.
The following is an implementation in C++:
template
- include
- include
void bogosort(std::vector & array) { while (! is_sorted(array)) std::random_shuffle(array.begin(), array.end());}template
bool is_sorted(const std::vector & array) { for (typename std::vector}::size_type i = 1; i < array.size(); ++i) if (array[i] < array[i-1]) return false; return true;