|Worst case performance||Unbounded|
|Best case performance||θ(n)|
|Average case performance||O((n+1)!)|
|Worst case space complexity||O(n)|
In computer science, bogosort (also stupid sort, slowsort, random sort, shotgun sort or monkey sort) 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.
Description of the algorithm
The following is a description of the algorithm in pseudocode:
while not isInOrder(deck): shuffle(deck)
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 , 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.
- 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 value of the total number of times this operation needs to be done is equal to the number of misplaced elements.
- is an algorithm that was designed not to succeed before the heat death of the universe on any sizable list. It works by recursively calling itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The base case is a single element, which is always sorted. For other cases, it compares the last element to the maximum element from the previous elements in the list. If the last element is greater or equal, it checks if the order of the copy matches the previous version, copies back if not, and returns. Otherwise, it reshuffles the current copy of the list and goes back to its recursive check.
- 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 a bozosort 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). First, use quantum randomness to permute the list. The quantum randomization creates n! branches of the wavefunction ("universes" in many-worlds interpretation), and one of these will be such that this single shuffle had produced the list in sorted order. The list is then inspected, and if it is not sorted, the universe is destroyed. Since destroyed universes cannot be observed, the list is always observed to have been successfully sorted after one iteration in O(n) which is just the time needed to verify that the list is sorted. Besides the impracticability of this algorithm, it is also not technically possible. Permuting n! items requires n*log(n) bits of randomness (see Stirling's approximation), so the algorithm would require O(n*log(n)) time. Beyond this, quantum computers do not actually offer a way to "destroy a universe": doing so would offer an algorithm for quantum computers to run NP-complete problems in polynomial time, a task which is widely suspected to be impossible. Instead, they can only "destroy possibilities" through quantum interference, yielding the complexity classes EQP and BQP. If destroying the universe is interpreted as killing all life, e.g. via nuclear winter, then the algorithm can work in O(n*log(n)) time through the anthropic principle.
- Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17.
- Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF), SIGPLAN Notices, pp. 192–203, doi:10.1145/1086365.1086390
- E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
- Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111.
- Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne, CiteSeerX: 10
.1 .1 .54 .2347.
- "Bogosort". The Jargon File 4.4.8. 2003. Retrieved 11 April 2013.
- Google Code Jam 2011, Qualification Rounds, Problem D
- archived version of mathNEWS Issue 111.3: Friday, October 23, 2009 - Quantum Bogosort
|The Wikibook Algorithm Implementation has a page on the topic of: Bogosort|
- BogoSort on WikiWikiWeb
- Inefficient sort algorithms
- Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
- Bogosort and jmmcg::bogosort: Simple, yet perverse, C++ implementations of the bogosort algorithm.