Богосорт - Bogosort

Богосорт
Класс	Сортировка
Структура данных	Массив
Худший случай спектакль	Неограниченный (рандомизированная версия), О((п+1)!) (ожидаемое время выполнения, рандомизированная версия) О((п+1)!) (детерминированная версия)
Лучший случай спектакль	О(п)
Средний спектакль	О((п+1)!)
Худший случай космическая сложность	О(1)

В Информатика, Богосорт^[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 когда-либо запускается на квантовом компьютере и после итерации список все еще не отсортирован. Однако на самом деле ничего не произошло.

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

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

^ ^а ^б ^c ^d ^е ^ж ^г Gruber, H .; Holzer, M .; Рупп, О., "Сортировка медленным способом: анализ извращенно ужасных алгоритмов рандомизированной сортировки", 4-я Международная конференция по развлечениям с алгоритмами, Кастильончелло, Италия, 2007 г. (PDF), Конспект лекций по информатике, 4475, Springer-Verlag, стр. 183–197, Дои:10.1007/978-3-540-72914-3_17.
^ ^а ^б Киселев Олег; Шан, Чжун-цзе; Friedman, Daniel P .; Сабри, Амр (2005), "Обратное отслеживание, чередование и завершающие преобразователи монад: (функциональная жемчужина)", Труды Десятой Международной конференции ACM SIGPLAN по функциональному программированию (ICFP '05) (PDF), Уведомления SIGPLAN, стр. 192–203, Дои:10.1145/1086365.1086390, S2CID 1435535, заархивировано из оригинал (PDF) 26 марта 2012 г., получено 22 июн 2011
^ Э. С. Раймонд. "бого-сорт". Словарь нового хакера. MIT Press, 1996.
^ ^а ^б Найш, Ли (1986), "Отрицание и кванторы в NU-Prolog", Труды Третьей Международной конференции по логическому программированию., Конспект лекций по информатике, 225, Springer-Verlag, стр. 624–634, Дои:10.1007/3-540-16492-8_111.
^ "богосорт". xlinux.nist.gov. Получено 11 ноября 2020.
^ Google Code Jam 2011, квалификационные раунды, задача D
^ Богобогосорт
^ Лерма, Мигель А. (2014). «Насколько неэффективным может быть алгоритм сортировки?». arXiv:1406.1077 [cs.DS ].

^ Противоположность «оптимальному»

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

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

[Fun07-1] а ^б ^c ^d ^е ^ж ^г Gruber, H .; Holzer, M .; Рупп, О., "Сортировка медленным способом: анализ извращенно ужасных алгоритмов рандомизированной сортировки", 4-я Международная конференция по развлечениям с алгоритмами, Кастильончелло, Италия, 2007 г. (PDF), Конспект лекций по информатике, 4475, Springer-Verlag, стр. 183–197, Дои:10.1007/978-3-540-72914-3_17.

[KSFS-2] а ^б Киселев Олег; Шан, Чжун-цзе; Friedman, Daniel P .; Сабри, Амр (2005), "Обратное отслеживание, чередование и завершающие преобразователи монад: (функциональная жемчужина)", Труды Десятой Международной конференции ACM SIGPLAN по функциональному программированию (ICFP '05) (PDF), Уведомления SIGPLAN, стр. 192–203, Дои:10.1145/1086365.1086390, S2CID 1435535, заархивировано из оригинал (PDF) 26 марта 2012 г., получено 22 июн 2011

[3] Э. С. Раймонд. "бого-сорт". Словарь нового хакера. MIT Press, 1996.

[Naish86-4] а ^б Найш, Ли (1986), "Отрицание и кванторы в NU-Prolog", Труды Третьей Международной конференции по логическому программированию., Конспект лекций по информатике, 225, Springer-Verlag, стр. 624–634, Дои:10.1007/3-540-16492-8_111.

[5] "богосорт". xlinux.nist.gov. Получено 11 ноября 2020.

[6] Google Code Jam 2011, квалификационные раунды, задача D

[7] Богобогосорт

[9] Лерма, Мигель А. (2014). «Насколько неэффективным может быть алгоритм сортировки?». arXiv:1406.1077 [cs.DS ].

[pessimal-8] Противоположность «оптимальному»

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[а]

[8]

Алгоритмы сортировки
Теория	Теория вычислительной сложности Обозначение Big O Общий заказ Списки Замена Стабильность Сравнительная сортировка Адаптивная сортировка Сортировочная сеть Целочисленная сортировка X + Y сортировка Трансдихотомическая модель Квантовая сортировка
Обменные сорта	Пузырьковая сортировка Сорт коктейльный шейкер Нечетно-четная сортировка Сортировка гребней Сортировка гномов Быстрая сортировка Slowsort Stooge sort Богосорт
Выборочные сорта	Выборочная сортировка Heapsort Smoothsort Сортировка декартовых деревьев Сортировка турнира Цикл сортировки Сортировка слабой кучи
Вставки	Вставка сортировки Shellsort Сортировка Сортировка дерева Сортировка библиотеки Сортировка терпения
Сортировка слияния	Сортировка слиянием Каскадная сортировка слиянием Осциллирующая сортировка слиянием Полифазная сортировка слиянием
Виды распространения	Американский флаг сортировка Сортировка бисера Ковшовая сортировка Burstsort Счетная сортировка Сортировка интерполяции Сорт голубятни Proxmap сортировка Radix sort Flashsort
Параллельные сортировки	Bitonic сортировщик Сортировка по четным и нечетным дозаторам Сеть попарной сортировки Samplesort
Гибридные сорта	Блокировать сортировку слиянием Сорт Киркпатрика-Райша Тимсорт Интросорт Spreadsort Сортировка слиянием-вставкой
Другой	Топологическая сортировка Предпотопологический порядок Сортировка блинов Сортировка спагетти