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

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

Випадкове сортування (англ. 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!) (в припущенні, що всі елементи масиву різні). Також час роботи алгоритму залежить від того скільки різних елементів присутні в масиві, і як часто кожен з них зустрічається. За лемою Бореля-Кантеллі, алгоритм завжди знайде правильне впорядкування (можливо за дуже велику кількість кроків).

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


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.
Комедія Це незавершена стаття про гумор, комедію або сатиру.
Ви можете допомогти проекту, виправивши або дописавши її.