In computer science, bogosort (also random sort) is a particularly ineffective sorting algorithm. Its only use is for educational purposes, to contrast it with other more realistic algorithms. Used to sort a deck of cards, it would consist of checking if the deck is in order, and if it's not, throwing the deck into the air, picking the cards up at random, and repeating the process. It is named after the humorous term quantum bogodynamics and, ultimately, the word bogus.
Implementation
In pseudocodewhile not InOrder(deck) do Shuffle(deck);
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!. 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. For dealing with a list of two elements, this places Bogosort amongst the best sorting methods: one comparison, and then either it finishes, or else there's one swap and one more comparison. If that second comparison were omitted, then the best possible sequence would be attained.
The exact expected running time depends on how many different element values occur, and how often each of them occurs, but one might expect that for non-trivial cases the expected running time is super-exponential in n since n! outgrows an for every constant a.
It terminates for the same reason that the infinite monkey theorem holds; there's some probability of getting the right permutation, so given an unbounded number of tries it must eventually be stumbled upon. For this though, the shuffle process must never repeat its pattern, which will happen if it relies upon random number generators that are not perfect, as are all pseudo-random generators.
Related algorithms
Bozo sort
Bozo sort is another sorting algorithm based on random numbers. If the list isn't 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.
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, isn't infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer triggers its "destroy universe" operation. Only in the surviving universes will there be observers to see that the randomization worked first time and that the list is in sorted order.
Note, however, that even here there's 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.
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.
