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; }
Search Encyclopedia
|
Featured Article
|