Bogosort
|
|
According to the Jargon File, bogo-sort 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
from random import shuffle
def bogosort(seq):
while seq != sorted(seq):
shuffle(seq)
Java
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
public class Bogosort
{
protected boolean isSorted (List array, Comparator cmp)
{
Iterator i = array.iterator();
Object cur = null, next = i.next();
while (i.hasNext()) {
cur = next;
next = i.next();
if (cmp.compare(cur, next) > 0)
return false;
}
return true;
}
protected void bsort (List array, Comparator cmp)
{
do {
Collections.shuffle(array);
} while (!isSorted(array, cmp));
}
public void sort (Object [] array, Comparator cmp)
{
if (array.length > 0)
bsort (Arrays.asList(array), cmp);
}
}
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;
}
Perl
sub bogosort {
my @a = @_;
while( ! is_sorted(@a) ) {
shuffle(\@a);
}
@a;
}
sub is_sorted {
for( my $ctr = 1; $ctr <= $#_; $ctr++ ) {
return if $_[$ctr-1] > $_[$ctr];
}
1;
}
sub shuffle {
my $ref = shift;
for( my $ctr = 0; $ctr < $#{$ref}; $ctr++ ) {
my $index = $ctr + int(rand($#{$ref} - $ctr + 1));
my $temp = $ref->[$ctr];
$ref->[$ctr] = $ref->[$index];
$ref->[$index] = $temp;
}
}
External links
- Jargon File entry for bogo-sort (http://www.catb.org/~esr/jargon/html/B/bogo-sort.html)