Bogosort (also random sorting , gun sorting or monkey sorting ) is a very inefficient sorting algorithm. It is used only for educational purposes, opposing other, more realistic algorithms. If bogosort is used to sort a deck of cards, then first in the algorithm you need to check whether all cards lie in order, and if they do not lie, then randomly mix it, check whether all cards are now in order, and repeat the process until the deck is sorted .
The average time of the algorithm
With the cycle once per second, sorting out the following number of elements on average can take:
| Number of items | one | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten | eleven | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Average time | 1 s | 4 s | 18 s | 96 s | 10 min | 1.2 h | 9.8 h | 3.7 days | 37.8 days | 1.15 years | 13.9 years | 182 years |
When running a 4-core processor at 2.4 GHz (9.6 billion operations per second):
| Number of items | ten | eleven | 12 | 13 | 14 | 15 | sixteen | 17 | 18 | nineteen | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Average time | 0.0037 s | 0.045 s | 0.59 s | 8.4 s | 2.1 min | 33.6 min | 9.7 h | 7.29 days | 139 days | 7.6 years | 160 years |
A deck of 32 cards will be sorted by a computer with an average of 2.7⋅10 19 years.
Implementation Example
int correct ( int * arr , int size ) { while ( size -> 0 ) if ( arr [ size - 1 ] > arr [ size ]) return 0 ; return 1 ; } void shuffle ( int * arr , int size ) { for ( int i = 0 ; i < size ; ++ i ) swap ( arr [ i ], arr [( rand () % size )]); } void bogoSort ( int * arr , int size ) { while ( ! correct ( arr , size )) shuffle ( arr , size ); } See also
- Las Vegas (algorithm)
- Pseudo Random Number Generators
Links
- Bogosort / Jargon File (eng.)
- Max Sherman Bogo-sort is Sort of Slow , June 2013 (Eng.)
- Hermann Gruber, Markus Holzer, and Oliver Ruepp, Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms , 2007. (English)
- Rahul Agrawal, https://www.geeksforgeeks.org/bogosort-permutation-sort/ (eng.)
- Impractical sorting - senseless and merciless / valemak, October 18, 2013