Богосорт - Bogosort

В Информатика, Богосорт^[1][2] (также известен как перестановочная сортировка, глупый вид,^[3] медленная сортировка,^[4] дробовик сортировка, случайная сортировка, обезьяны, бобосорт, lawn_gnoome sort или сортировка в случайном порядке или сумасшедшая сортировка) является крайне неэффективным алгоритм сортировки на основе генерировать и тестировать парадигма. Функция последовательно генерирует перестановки его ввода, пока он не найдет тот, который отсортирован. Он бесполезен для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его более эффективным алгоритмам.

Существуют две версии этого алгоритма: детерминированная версия, которая перечисляет все перестановки, пока не попадет в отсортированную,^[2][4] и рандомизированный версия, которая случайным образом меняет свой ввод. Аналогия работы последней версии - отсортировать колода карт подбрасывая колоду в воздух, случайным образом выбирая карты и повторяя процесс, пока колода не будет отсортирована. Его имя - чемодан слов фальшивка и Сортировать.^[5]

Описание алгоритма

Ниже приводится описание рандомизированного алгоритма в псевдокод:

в то время как не isInOrder (колода): перемешать (колода)

Вот псевдокод выше, переписанный на Python 3:

от случайный импорт тасоватьdef отсортировано(данные) -> bool:    "" "Определить, отсортированы ли данные." ""    вернуть все(данные[я] <= данные[я + 1] для я в ассортимент(len(данные) - 1))def Богосорт(данные) -> список:    "" "Перемешать данные до сортировки." ""    в то время как не отсортировано(данные):        тасовать(данные)    вернуть данные

В этом коде предполагается, что данные представляют собой простой изменяемый тип данных, как встроенный в Python список- чьи элементы можно без проблем сравнивать.

Вот пример с перемешиванием в Стандартный ML:

 вал _ = грузить "Случайный"; грузить "Инт"; вал rng = Случайный.Newgen (); весело Выбрать (y :: xs, 0) = (у, хз)   | Выбрать (x :: xs, я) = позволять вал (у, хз ') = Выбрать (хз, я-1) в (у, x :: xs ') конец   | Выбрать (_, я) = поднять Провал ("Коротко" ^ Int.нанизывать я ^ "элементы".); (* Восстанавливает список в случайном порядке, удаляя элементы в случайных позициях *) весело тасовать хз =    позволять весело rtake [] _ = []          | rtake ys Максимум =             позволять вал (у, ys ') = Выбрать (ys, Случайный.ассортимент (0, Максимум) rng)             в у :: rtake ys ' (Максимум-1)             конец    в rtake хз (длина хз) конец; весело Богосорт хз комп =  позволять весело isSorted (x :: y :: xs) комп = комп(Икс,у) <> БОЛЬШЕ а также isSorted (y :: xs) комп       | isSorted _ комп = правда;     вал а = ссылка хз; в в то время как(не(isSorted (! а) комп)) делать (  а := тасовать (! а)  ); (! а) конец;

Время работы и окончание

Экспериментальное время выполнения богосорта

Если все элементы для сортировки различны, ожидаемое количество сравнений, выполненных в среднем случае с помощью рандомизированной богосортировки, равно асимптотически эквивалентен ${ Displaystyle (е-1) п!}$, а ожидаемое количество свопов в среднем случае равно ${ Displaystyle (п-1) п!}$.^[1] Ожидаемое количество свопов растет быстрее, чем ожидаемое количество сравнений, потому что, если элементы не в порядке, это обычно обнаруживается после нескольких сравнений, независимо от того, сколько элементов имеется; но работа по перемешиванию коллекции пропорциональна ее размеру. В худшем случае количество сравнений и свопов не ограничено по той же причине, по которой брошенная монета может выпадать орлом любое количество раз подряд.

Наилучший случай имеет место, если данный список уже отсортирован; в этом случае ожидаемое количество сравнений равно ${ displaystyle n-1}$, и свопы вообще не производятся.^[1]

Для любой коллекции фиксированного размера ожидаемое время работы алгоритма конечно по той же причине, что и теорема о бесконечной обезьяне имеет место: существует некоторая вероятность получения правильной перестановки, поэтому при неограниченном количестве попыток она будет почти наверняка в итоге будет выбран.

Связанные алгоритмы

Горосорт

алгоритм сортировки, представленный в 2011 г. Google Code Jam.^[6] Пока список не упорядочен, подмножество всех элементов переставляется случайным образом. Если это подмножество оптимально выбирать каждый раз, когда это выполняется, ожидаемое значение из общего числа раз, которое необходимо выполнить эту операцию, равно количеству неправильно установленных элементов.

Богобогосорт

это алгоритм, который был разработан так, чтобы не иметь успеха до тепловая смерть вселенной в любом значительном списке. Он работает, рекурсивно вызывая себя с все меньшими и меньшими копиями начала списка, чтобы увидеть, отсортированы ли они. Базовый вариант - это отдельный элемент, который всегда сортируется. В других случаях он сравнивает последний элемент с максимальным элементом из предыдущих элементов в списке. Если последний элемент больше или равен, он проверяет, соответствует ли порядок копии предыдущей версии, и если да, то возвращается. В противном случае он перетасовывает текущую копию списка и перезапускает рекурсивную проверку.^[7]

Bozosort

- еще один алгоритм сортировки, основанный на случайных числах. Если список не в порядке, он выбирает два элемента случайным образом и меняет их местами, а затем проверяет, отсортирован ли список. Анализ времени работы бозосорта сложнее, но некоторые оценки можно найти в анализе Х. Грубером «извращенно ужасных» алгоритмов рандомизированной сортировки.^[1] O (n!) Оказывается ожидаемым средним случаем.

Worstsort

пессимальный^[а] алгоритм сортировки, который гарантированно завершится за конечное время; однако не существует вычислимого предела неэффективности алгоритма сортировки, и поэтому он более пессимален, чем другие описанные здесь алгоритмы. В ${ displaystyle { text {worstsort}}}$ алгоритм основан на плохом алгоритме сортировки, ${ displaystyle { text {badsort}}}$. Алгоритм плохой сортировки принимает два параметра: ${ displaystyle L}$, который является списком для сортировки, и ${ displaystyle k}$, которая является глубиной рекурсии. На уровне рекурсии ${ displaystyle k = 0}$, ${ displaystyle { text {badsort}}}$ просто использует общий алгоритм сортировки, такой как пузырьковая сортировка, чтобы отсортировать входные данные и вернуть отсортированный список. То есть, ${ displaystyle { text {badsort}} (L, 0) = { text {bubbleort}} (L)}$. Следовательно, временная сложность плохой сортировки равна ${ Displaystyle О влево (п ^ {2} вправо)}$ если ${ displaystyle k = 0}$. Однако для любого ${ displaystyle k> 0}$, ${ displaystyle { text {badsort}} (L, k)}$ первый генерирует ${ displaystyle P}$, список всех перестановок ${ displaystyle L}$. Потом, ${ displaystyle { text {badsort}}}$ вычисляет ${ displaystyle { text {badsort}} (P, k-1)}$, и возвращает первый элемент отсортированного ${ displaystyle P}$. Делать ${ displaystyle { text {worstsort}}}$ действительно пессимально, ${ displaystyle k}$ может быть присвоено значение вычислимой возрастающей функции, такой как ${ Displaystyle е двоеточие mathbb {N} to mathbb {N}}$ (например. ${ Displaystyle е (п) = А (п, п)}$, где ${ displaystyle A}$ является Функция Аккермана ). Следовательно, чтобы отсортировать список произвольно плохо, вы должны выполнить ${ displaystyle { text {worstsort}} (L, f) = { text {badsort}} (L, f ({ text {length}} (L)))}$, где ${ displaystyle { text {length}} (L)}$ = количество элементов в ${ displaystyle L}$. Полученный алгоритм имеет сложность ${ Displaystyle Омега влево ( влево (п! ^ {(е (п))} вправо) ^ {2} вправо)}$, где ${ displaystyle n! ^ {(m)} = ( dotso ((n!)!)! dotso)!}$ = факториал ${ displaystyle n}$ повторяется ${ displaystyle m}$ раз. Этот алгоритм можно сделать сколь угодно неэффективным, выбрав достаточно быстрорастущую функцию ${ displaystyle f}$.^[8]

Slowsort

Другой юмористический алгоритм сортировки, использующий ошибочную стратегию «разделяй и властвуй» для достижения огромной сложности.

Quantum BogoSort

Quantum BogoSort - это в шутку о разрушении вселенной, если алгоритм BogoSort когда-либо запускается на квантовом компьютере и после итерации список все еще не отсортирован. Однако на самом деле ничего не произошло.

Смотрите также

• Алгоритм Лас-Вегаса
• Stooge sort

использованная литература

внешние ссылки

• BogoSort на WikiWikiWeb
• Неэффективные алгоритмы сортировки
• Богосорт: реализация, работающая на Unix-подобный системы, аналогичные стандартным Сортировать программа.
• Богосорт и jmmcg :: bogosort^{[постоянная мертвая ссылка ]}: Простая, но извращенная реализация алгоритма богосорта на C ++.
• Пакет Богосорт НПМ: реализация bogosort для экосистемы Node.js.
• Макс Шерман Бого-сортировка вроде медленная, Июнь 2013