Випадкове сортування

Випадкове сортування (англ. Bogosort)^[1][2] — неефективний на практиці гумористичний алгоритм сортування. Наочно використовується для впорядкування колоди карт таким чином: колода підкидається у повітря, карти збираються у довільному порядку і перевіряється, чи є колода впорядкованою. Якщо колода невпорядкована, то операцію повторюють.

Алгоритм має й інші назви: сортування бозо (англ. bozo sort), дурне сортування (англ. stupid sort), мавпяче сортування (англ. monkey sort), випадкове сортування (англ. random sort), сортування п'яниці (англ. drunk man sort).

Випадкове сортування не є стабільним.

Псевдокод

${\displaystyle \;BogoSort(A)}$
1 while not ${\displaystyle \;is\_sorted(A)}$
2       do ${\displaystyle A\gets \;Random\_Permutation(A)}$

Функція ${\displaystyle \;is\_sorted(A)}$ повертає значення істина, якщо масив ${\displaystyle \;A}$ впорядкований, а функція ${\displaystyle \;Random\_Permutation(A)}$ повертає випадкову перестановку елементів масиву.

Час роботи

Одна ітерація алгоритму потребує часу ${\displaystyle \;O(n)}$ — найкращий можливий час роботи. В середньому алгоритм буде працювати: ${\displaystyle n\cdot \sum _{i=1}^{\infty }{{\frac {i}{n!}}\cdot (1-{\frac {1}{n!}})^{i-1}}=O(n\cdot \;n!)}$ (в припущенні, що всі елементи масиву різні). Також час роботи алгоритму залежить від того скільки різних елементів присутні в масиві, і як часто кожен з них зустрічається. За лемою Бореля — Кантеллі, алгоритм завжди знайде правильне впорядкування (можливо за дуже велику кількість кроків).

Проте, слід зауважити, що в комп'ютерах використовуються не справжні випадкові числа а їх аналоги (псевдовипадкові числа). Тому комп'ютерна реалізація випадкового сортування може ніколи не завершити роботу.