Bogosort

Bogosort
Bogosort
Class Sorting algorithm
Data structure Array
Worst case performance O(\infin)[1]
Best case performance Ω(n)[1]
Average case performance O(n × n!)[1]
Worst case space complexity O(n)

In computer science, bogosort[1][2] (also stupid sort[3] or slowsort[4][5]) is a particularly ineffective sorting algorithm based on the generate and test paradigm. It is not useful for sorting, but may be used for educational purposes, to contrast it with other more realistic algorithms; it has also been used as an example in logic programming.[2][4][5] 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, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. Its name comes from the word bogus.

Contents

Description of the algorithm

Following is a description of the algorithm in pseudocode.

while not inOrder(deck) do
    shuffle(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

Goro sort
is a sorting algorithm introduced in the 2011 Google Code Jam.[6] As long as the list is not in order, a subset of all elements is randomly permuted. If this subset is optimally chosen each time this is performed, the expected value of the total number of times this operation needs to be done is equal to the number of misplaced elements.
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] O(n!) is found to be the expected average case.
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. The list is then inspected, and if it is not in order, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns 2N (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.

See also

References

  1. ^ a b c d e f g Gruber, H.; Holzer, M.; Ruepp, O., "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, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17, http://www.hermann-gruber.com/data/fun07-final.pdf .
  2. ^ a b Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05), SIGPLAN Notices, pp. 192–203, doi:10.1145/1086365.1086390, http://www.dicta.org.uk/programming/LogicT.pdf 
  3. ^ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
  4. ^ a b Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111 .
  5. ^ a b Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.2347 .
  6. ^ Google Code Jam 2011, Qualification Rounds, Problem D

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Bogosort — (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort… …   Википедия

  • Bogosort — Bogosort, Monkeysort oder Stupidsort bezeichnet ein nicht stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der Prototyp eines schlechten Algorithmus.… …   Deutsch Wikipedia

  • Randomsort — Der Begriff Bogosortierung oder englisch Bogosort (manchmal auch Stupidsort) bezeichnet ein nicht stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der …   Deutsch Wikipedia

  • Stupidsort — Der Begriff Bogosortierung oder englisch Bogosort (manchmal auch Stupidsort) bezeichnet ein nicht stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der …   Deutsch Wikipedia

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”