Сортування Бого

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

Сортування Бого не є стабільним.

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


1 while not 
2       do

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

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

Отримано з http://uk.wikipedia.org../../../%D1%81/%D0%BE/%D1%80/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%91%D0%BE%D0%B3%D0%BE_217d.html

Категорія: Алгоритми сортування

Сортування Бого

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

Views

Навігація

Участь

Пошук

Іншими мовами