Bogosort

Time you got around to sponsoring a child

According to the Jargon File, the 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. Another name is bozo sort.

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 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(array):

    for i in range(1, len(array)):

        if (array[i] < array[i-1]):

            return False

    return True

def bogosort(array):

    while not is_sorted(array):

        random.shuffle(array)

C++

#include

#include

template

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;

External links

Jargon File entry for bogo-sort