Bogosort

From Wikipedia, the free encyclopedia

In computer science, bogosort (also random sort) is a particularly ineffective sorting algorithm. Its only use is for educational purposes, to contrast it with other more realistic algorithms. Used to sort a deck of cards, it would consist of checking if the deck is in order, and if it's not, throwing the deck into the air, picking the cards up at random, and repeating the process. It is named after the humorous term quantum bogodynamics and, ultimately, the word bogus.

[edit] Implementation

In pseudocode

while not InOrder(deck) do Shuffle(deck);

[edit] Java

public int[] BogoSort(int[] N)
{
    Random rnd = new Random();
    while(true)
    {
        boolean sorted = true;
        for(int i = 0; i < N.length-1; i++)
            if(N[i] > N[i+1]){
                sorted = false;
                break;
            }
        if (sorted)
            return N;
        for(int i = N.length - 1; i > 0; i--)
        {
            int rand = rnd.nextInt(i);
            int temp = numbers[i];
            numbers[i] = numbers[rand];
            numbers[rand] = temp;
        }
    }
}

[edit] Running time and termination

This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected number of comparisons in the average case is asymptotically equivalent to (e-1)× n!, and the expected number of swaps in the average case equals (n-1)×n!.^[1] The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons no matter how many elements there are, but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.

The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is n-1, and no swaps at all are carried out.^[1] For dealing with a list of two elements, this places Bogosort amongst the best sorting methods: one comparison, and then either it finishes, or else there is one swap and one more comparison. If that second comparison were omitted, then the best possible sequence would be attained.

The exact expected running time depends on how many different element values occur, and how often each of them occurs, but one might expect that for non-trivial cases the expected running time is super-exponential in n since n! outgrows aⁿ for every constant a. It terminates for the same reason that the infinite monkey theorem holds; there is some probability of getting the right permutation, so given an unbounded number of tries it must eventually be stumbled upon. For this though, the shuffle process must never repeat its pattern, which will happen if it relies upon random number generators that are not perfect, as are all pseudo-random generators.

[edit] Related algorithms

[edit] Random sort

Random Sort is a formal definition of the underlying algorithm, originally published^[2] by Mathijs Schmittmann. The article describes issues regarding complexity, possible applications with Quantum Inferference and a real-world example in a popular programming language.

[edit] Bozo sort

Bozo sort is another sorting algorithm based on random numbers. If the list is not in order, it picks two items at random and swaps them, then checks to see if the list is sorted. The running time analysis of Bozo Sort is more difficult, but some estimates are found in H. Gruber's analysis of perversely awful randomized sorting algorithms.^[1]

[edit] Quantum Bogosort

An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes and some of these will be such that the single shuffle had produced the list in sorted order because the total number of distinct orderings, though large, is not infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer triggers its "destroy universe" operation. Only in the surviving universes will there be observers to see that the randomization worked first time and that the list is in sorted order.

Note, however, that even here there is no free lunch -- while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness.

[edit] References

1. ^ ^{a b c} H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.
2. ^ M. Schmittmann: Formal Definition of Random Sort, 2008

[edit] External links

• Jargon File entry for bogo-sort, "the archetypal perversely awful algorithm"
• http://c2.com/cgi/wiki?BogoSort
• Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.

v • d • e Sorting algorithms Theory Computational complexity theory | Big O notation | Total order | Lists | Stability | Comparison sort Exchange sorts Bubble sort | Cocktail sort | Odd-even sort | Comb sort | Gnome sort | Quicksort Selection sorts Selection sort | Heapsort | Smoothsort | Strand sort Insertion sorts Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting Merge sorts Merge sort Non-comparison sorts Radix sort | Bucket sort | Counting sort | Pigeonhole sort | Tally sort Others Topological sorting | Sorting network | Bitonic sorter Ineffective/jokeful sorts Bogosort