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 Black.
Entry modified 30 September 2013.
HTML page formatted Mon Nov 18 10:44:09 2013.
Cite this as:
Paul E. Black, "bogosort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 September 2013. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bogosort.html