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

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

Алгоритм має й інші назви: сортування бозо (Шаблон:Lang-en), дурне сортування (Шаблон:Lang-en), мавпяче сортування (Шаблон:Lang-en), випадкове сортування (Шаблон:Lang-en), сортування п'яниці (Шаблон:Lang-en).

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

Псевдокод

$BogoSort(A)$
1 while not $is\mathrm{\_}sorted(A)$
2       do $A\leftarrow Random\mathrm{\_}Permutation(A)$

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

Час роботи

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

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

Посилання

• Реалізація випадкового сортування на мові C#. Шаблон:Webarchive