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

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

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

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

Примітки Редагувати

↑ Gruber, H.; Holzer, M.; Ruepp, O. Sorting the slow way: an analysis of perversely awful randomized sorting algorithms. 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007. Lecture Notes in Computer Science 4475. Springer-Verlag. с. 183–197. doi:10.1007/978-3-540-72914-3_17. .
↑ Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005). Backtracking, interleaving, and terminating monad transformers: (functional pearl). Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05). SIGPLAN Notices. с. 192–203. doi:10.1145/1086365.1086390. Архів оригіналу за 26 березня 2012. Процитовано 22 червня 2011.

Посилання Редагувати

Реалізація випадкового сортування на мові C#. [Архівовано 13 квітня 2019 у Wayback Machine.]

Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.

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

[Fun07-1] Gruber, H.; Holzer, M.; Ruepp, O. Sorting the slow way: an analysis of perversely awful randomized sorting algorithms. 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007. Lecture Notes in Computer Science 4475. Springer-Verlag. с. 183–197. doi:10.1007/978-3-540-72914-3_17. .

[KSFS-2] Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005). Backtracking, interleaving, and terminating monad transformers: (functional pearl). Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05). SIGPLAN Notices. с. 192–203. doi:10.1145/1086365.1086390. Архів оригіналу за 26 березня 2012. Процитовано 22 червня 2011.

[1]

[2]