Encyclopedia > Bogosort

  Article Content


According to the Jargon File, the bogosort is "the archetypal perversely awful algorithm", equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It is named after the humourous term quantum bogodynamics.

This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n!). The algorithm may finish in O(n) if you are extremely lucky, or if all elements are equal. 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++:

#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;

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Sanskrit language

... (t, th, d, dh, n) Labial (with the lips[?]) (p, ph, b, bh, m) It also has four semivowels: y, r, l, v. All of these but r have nasalized forms. Sanskrit also has ...

This page was created in 36.4 ms