NIST

bogosort

(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

Implementation

(Python).

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 21 April 2022.
HTML page formatted Thu Apr 21 14:52:02 2022.

Cite this as:
Paul E. Black, "bogosort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 21 April 2022. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bogosort.html