Bogosort

According to the Jargon File, bogosort is "the archetypal perversely awful algorithm", one example of which is attempting to sort a deck of cards by repeatedly throwing the deck in the air, picking the cards up at random, and then testing whether the cards are in sorted order. It is named after the humourous term quantum bogodynamics and ultimately, the word bogus. Other names are bozo sort and blort sort.

Here is the pseudocode of the algorithm:

 function bogosort(array)
   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 terminates for the same reason that the infinite monkey theorem holds; there is some probability of getting the right permutation, so given an infinite number of tries it must eventually find it.

It should be noted that with real-world pseudo-random number algorithms, which have a finite number of states and are not in any case actually random, the algorithm may never terminate for certain inputs.

Bogosort is not a stable sort.

Implementations

Python

import random

def is_sorted(aList):
    sortedCopy = aList[:]
    sortedCopy.sort()
    return sortedCopy == aList

def bogosort(aList):
    while not is_sorted(aList):
        random.shuffle(aList)

C++

#include <algorithm>
#include <vector>

template<class T>
void bogosort(std::vector<T>& array)
{
    while (! is_sorted(array))
        std::random_shuffle(array.begin(), array.end());
}

template<class T>
bool is_sorted(const std::vector<T>& array)
{
    for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
        if (array[i] < array[i-1]) return false;
    return true;
}

External links

• Jargon File entry for bogo-sort