bogosort
Sign in to saveIn computer science, bogosort (also known as permutation sort and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. The algorithm's name is a portmanteau of the words bogus and sort.
Key facts
- Algorithm.class
- Sorting
- Algorithm.data
- Array
- Algorithm.time
- Unbounded (randomized version), \Omicron(n \times n!) (deterministic version)
- Algorithm.average time
- \Theta(n \times n!)
- Algorithm.best time
- \Omega(n)
- Algorithm.space
- \Omicron(1)
via Wikipedia infobox
Article
10 sectionsContents
- Probabilistic analysis
- Description of the algorithm
- Pseudocode
- C
- Python
- Running time and termination
- Related algorithms
- See also
- References
- External links
In computer science, bogosort (also known as permutation sort and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. The algorithm's name is a portmanteau of the words bogus and sort.
Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input and checks whether it is sorted. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unlikely to occur.