Definition: A terribly inefficient sort algorithm that repeatedly generates a random permutation of the items until the items are in order.
Generalization (I am a kind of ...)
Las Vegas algorithm.
See also taco sort, bozo sort, stooge sort, lucky sort.
Note: From the slang "bogus" meaning "bad" as in "I can't believe anybody would be so thoughtless to write/do/say/believe that, and I just can't let it pass without objecting."
Fastest run time is Θ(n). Average run time is Ω(n × n!). From
Hermann Gruber, Markus Holzer, and Oliver Ruepp, Sorting the slow way: An analysis of perversely awful randomized sorting algorithms, FUN 2007, LNCS 4475, pp. 183-197, 2007. Available at http://www2.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf
Note: the permutation subroutine given for Algorithm 1 is Fisher-Yates shuffle. Also "Supercalifragilisticexpialidocious" is misspelled on the sixth page, although it is spelled correctly in the footnote.
Also called "stupid sort".
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 28 February 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "bogosort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 28 February 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bogosort.html