Bogosort
Encyclopedia
In computer science
, bogosort (also stupid sort or slowsort) is a particularly ineffective sorting algorithm
based on the generate and test
paradigm. It is not useful for sorting, but may be used for educational purposes, to contrast it with other more realistic algorithms; it has also been used as an example in logic programming
. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. Its name comes from the word bogus.
.
while not inOrder(deck) do
shuffle(deck);
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
, and the expected number of swaps in the average case equals 
. 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
, and no swaps at all are carried out.
For any collection of fixed size, the expected running time of the algorithm is finite for much 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 will almost surely
eventually be chosen. However, if a pseudorandom number generator
is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior.
of the total number of times this operation needs to be done is equal to the number of misplaced elements.
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. O(n!) is found to be the expected average case.
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. The list is then inspected, and if it is not in order, the universe is unbalanced. By the many-worlds interpretation
of quantum physics, the quantum randomization spawns
(where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, bogosort (also stupid sort or slowsort) is a particularly ineffective sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
based on the generate and test
Trial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
paradigm. It is not useful for sorting, but may be used for educational purposes, to contrast it with other more realistic algorithms; it has also been used as an example in logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. Its name comes from the word bogus.
Description of the algorithm
Following is a description of the algorithm in pseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
.
while not inOrder(deck) do
shuffle(deck);
Running time and termination
This sorting algorithmSorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
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
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
, and the expected number of swaps in the average case equals . 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
, and no swaps at all are carried out.For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem
Infinite monkey theorem
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare....
holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely
Almost surely
In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory...
eventually be chosen. However, if a pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior.
Related algorithms
Goro sort: is a sorting algorithm introduced in the 2011 Google Code Jam. As long as the list is not in order, a subset of all elements is randomly permuted. If this subset is optimally chosen each time this is performed, the expected valueExpected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
of the total number of times this operation needs to be done is equal to the number of misplaced elements.
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. O(n!) is found to be the expected average case.
Quantum bogosort: An in-joke
In-joke
An in-joke, also known as an inside joke or in joke, is a joke whose humour is clear only to people who are in a particular social group, occupation, or other community of common understanding...
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. The list is then inspected, and if it is not in order, the universe is unbalanced. By the many-worlds interpretation
Many-worlds interpretation
The many-worlds interpretation is an interpretation of quantum mechanics that asserts the objective reality of the universal wavefunction, but denies the actuality of wavefunction collapse. Many-worlds implies that all possible alternative histories and futures are real, each representing an...
of quantum physics, the quantum randomization spawns
(where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.External links
- BogoSort on WikiWikiWebWikiWikiWebWikiWikiWeb is a term that has been used to refer to four things: the first wiki, or user-editable website, launched on 25 March 1995 by Ward Cunningham as part of the Portland Pattern Repository ; the Perl-based application that was used to run it, also developed by Cunningham, which was the first...
- Inefficient sort algorithms
- Bogosort: an implementation that runs on Unix-likeUnix-likeA Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
systems, similar to the standard sortSort (Unix)sort is a standard Unix command line program that prints the lines of its input or concatenation of all files listed in its argument list in sorted order. Sorting is done based on one or more sort keys extracted from each line of input. By default, the entire input is taken as sort key...
program. - Bogosort and jmmcg::bogosort: Simple, yet perverse, C++ implementations of the bogosort algorithm.