Encyclopedia > Bogosort

  Article Content

Bogosort

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
Reformed churches

... Free Reformed Churches in North America[?] - (Dutch Reformed - CGKN) Netherlands Reformed Church[?] Orthodox Christian Reformed Church[?] (Dutch Reformed - GKN) ...

 
 
 
This page was created in 21.8 ms