24 lines
806 B
Plaintext
24 lines
806 B
Plaintext
{{Sorting Algorithm}}
|
|
|
|
;Task:
|
|
[[wp:Bogosort|Bogosort]] a list of numbers.
|
|
|
|
|
|
Bogosort simply shuffles a collection randomly until it is sorted.
|
|
|
|
"Bogosort" is a perversely inefficient algorithm only used as an in-joke.
|
|
|
|
Its average run-time is O(n!) because the chance that any given shuffle of a set will end up in sorted order is about one in ''n'' factorial, and the worst case is infinite since there's no guarantee that a random shuffling will ever produce a sorted sequence.
|
|
|
|
Its best case is O(n) since a single pass through the elements may suffice to order them.
|
|
|
|
|
|
Pseudocode:
|
|
'''while not''' InOrder(list) '''do'''
|
|
Shuffle(list)
|
|
'''done'''
|
|
|
|
<br>
|
|
The [[Knuth shuffle]] may be used to implement the shuffle part of this algorithm.
|
|
<br><br>
|