(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 ...)
sort algorithm, Las Vegas algorithm.
See also permutation sort, 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".
Gruber, Holzer, and Ruepp give the fastest run time as Θ(n) and the average run time as Ω(n × n!).
Also called "stupid sort".
Author: PEB
Bogo sort illustrated followed by a race between bogo sort and stooge sort.
The race between bogo sort and stooge sort starts here:
Timothy J. Rolfe, Algorithm Alley: Randomized Shuffling, Dr. Dobb's Journal, 25(1):113-114, January 2000.
Called "bogosort" in
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.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 5 April 2023.
HTML page formatted Wed Apr 5 13:02:12 2023.
Cite this as:
Paul E. Black, "bogosort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 5 April 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/bogosort.html