In computer science, bogosort (also random sort, shotgun sort or monkey sort) is a particularly ineffective sorting algorithm. Its only use is for educational purposes, to contrast it with other more realistic algorithms. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, one would throw the deck into the air, pick the cards up at random, and repeat the process until the deck is sorted. Its name comes from the word bogus.
Implementation
In pseudocode
while not InOrder(deck) do Shuffle(deck);
Python
from random import shuffle
# Bogo-sort deck in place
while not all(x <= y for x, y in zip(deck, deck[1:])):
shuffle(deck)
Java
Random random = new Random();
public void bogoSort(int[] n) {
while(!inOrder(n))shuffle(n);
}
public void shuffle(int[] n) {
for (int i = 0; i < n.length; i++) {
int swapPosition = random.nextInt(i + 1);
int temp = n[i];
n[i] = n[swapPosition];
n[swapPosition] = temp;
}
}
public boolean inOrder(int[] n) {
for (int i = 0; i < n.length-1; i++) {
if (n[i] > n[i+1]) return false;
}
return true;
}
Scheme
;; Uses plt-scheme
(define flag 0)
(define (bogosort to-sort)
(if (eq? #t (sorted? to-sort))
to-sort
(begin
(set! flag 0)
(bogosort (shuffle to-sort)))))
(define (sorted? to-sort)
(for ((i (in-range (- (vector-length to-sort) 1))))
(if (> (vector-ref to-sort i) (vector-ref to-sort (+ 1 i)))
(set! flag 1)
(set! flag flag)))
(if (eq? 0 flag)
#t
#f))
;; Fisher-Yates shuffle
(define (shuffle deck)
(let loop ((n (vector-length deck)) (shuff_deck deck))
(if (<= n 1)
shuff_deck
(begin
(set! n (- n 1))
(let* ([rand (random (+ 1 n))]
[tmp (vector-ref shuff_deck rand)]
)
(vector-set! shuff_deck rand (vector-ref shuff_deck n))
(vector-set! shuff_deck n tmp))
(loop n shuff_deck)))))
Running time and termination
This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected number of comparisons in the average case is asymptotically equivalent to (e − 1)n!, and the expected number of swaps in the average case equals (n − 1)n!.[1] The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons no matter how many elements there are, but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.
The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is n − 1, and no swaps at all are carried out.[1]
For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely eventually be chosen. However, if a pseudorandom number generator is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior.
Related algorithms
Bozo sort
Bozo sort is another sorting algorithm based on random numbers. If the list is not in order, it picks two items at random and swaps them, then checks to see if the list is sorted. The running time analysis of Bozo Sort is more difficult, but some estimates are found in H. Gruber's analysis of perversely awful randomized sorting algorithms.[1]
Quantum Bogosort
An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes and some of these will be such that the single shuffle had produced the list in sorted order because the total number of distinct orderings, though large, is not infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer destroys the universe.[2] The only observers will then be in the surviving universes and will see that the randomization worked the first time and that the list is in sorted order.
Note, however, that even here there is no free lunch – while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness. (It also assumes that destroying the universe is O(1) in operation - since it has to be executed at most once.)
See also
References
- ^ a b c H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.
- ^ Jargon File entry for bogo-sort, "the archetypal perversely awful algorithm"
External links
|
Sorting algorithms |
|
| Theory |
|
 |
|
| Exchange sorts |
|
|
| Selection sorts |
|
|
| Insertion sorts |
|
|
| Merge sorts |
|
|
| Non-comparison sorts |
|
|
| Others |
|
|
| Ineffective/humorous sorts |
|
|
