(algorithm)
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".
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 30 September 2013.
HTML page formatted Mon Feb 2 13:10:39 2015.
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