(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.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 8 September 2009.
HTML page formatted Tue Sep 8 09:07:25 2009.
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. 8 September 2009. (accessed TODAY)
Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/bogosort.html
