Bogosort(Болотная сортировка) алгоритм сортировки
 Скачать 0.93 Mb.
|
Bogosort(Болотная сортировка) – алгоритм сортировкиBogosort (от амер. комп. жарг. bogus — неработоспособный, нефункциональный, бесполезный) — неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. BogoSort, также известный как сортировка перестановок, медленная сортировка - является особенно неэффективным алгоритмом, основанным на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своих входных данных, пока не найдет отсортированные При прохождении цикла один раз в секунду сортировка следующего количества элементов в среднем может занять: Среднее время работы алгоритма Например, если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода. Колода в 32 карты будет сортироваться компьютером в среднем 2,7⋅1019 лет. Рассмотрим пример массива (3 2 5 1 0 4) 4 5 0 3 2 1 (1-е перемешивание) 4 1 3 2 5 0 (2 перетасовки) 1 0 3 2 5 4 (3-я перетасовка) 3 1 0 2 4 5 (4-е перемешивание) 1 4 5 0 3 2 (5-я перетасовка) 0 1 2 3 4 5 (nth shuffling) —— Сортированный массив Здесь n неизвестно, потому что алгоритм не знает, на каком этапе результирующая перестановка окажется отсортированной. |