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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Псевдокод[ред.ред. код]

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

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

Час роботи[ред.ред. код]

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

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