Богосорт

Богосорт
Учебный класс	Сортировка
Структура данных	Множество
Наихудшая производительность	Неограниченный (рандомизированная версия), $O ((n +1)!)$ (Детерминированная версия)
Лучшая производительность	$O (n)$ ^[1]
Средняя производительность	$О ((п +1)!)$ ^[1]
Сложность пространства в наихудшем случае	$О (1)$

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

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

Описание алгоритма [ править ]

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

пока не isInOrder (колода): тасовать (колода)

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

из  случайного  перемешивания импорта def  is_sorted ( data )  ->  bool :  "" "Определяет, отсортированы ли данные." ""  return  all ( data [ i ]  <=  data [ i  +  1 ]  for  i  in  range ( len ( data )  -  1 ))def  bogosort ( data )  ->  list :  "" "Перемешать данные до сортировки." ""  пока  не  is_sorted ( data ):  shuffle ( data )  вернуть  данные

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

Вот пример случайного воспроизведения в Standard ML :

 val  _  =  загрузить  "Случайно" ;  загрузить  "Int" ;  val  rng  =  Случайно . newgen  (); весело  выбрать  ( y :: xs ,  0 )  =  ( y ,  xs )  |  select  ( x :: xs ,  i )  =  let  val  ( y ,  xs ' )  =  select  ( xs ,  i- 1 )  in  ( y ,  x :: xs' )  end  |  select  (_,  i )  =  поднять  Fail  ( "Short by"  ^  Int .toString  i  ^  "элементы". ); (* Восстанавливает список в случайном порядке, удаляя элементы в случайном порядке *)  fun  shuffle  xs  =  let  fun  rtake  []  _  =  []  |  rtake  ys  max  =  let  val  ( y ,  ys ' )  =  select  ( ys ,  Random . range  ( 0 ,  max )  rng )  in  y  ::  rtake  ys'  ( max- 1 )  end  in rtake  xs  ( длина  xs )  end ; весело  bogosort  хз  Comp  =  пусть  прикольных  isSorted  ( х :: у :: хз )  комп  =  аккомпанемента ( х , у )  <>  GREATER  атакже  isSorted  ( у :: хз )  комп  |  isSorted  _  comp  =  true ;  val  a  =  ref  xs ;  in  while ( not ( isSorted  ( ! a )  comp ))  do  (  a : =  перемешать  ( ! a )  );  ( ! а )  конец ;

Время выполнения и прекращение [ править ]

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

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

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

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

Связанные алгоритмы [ править ]

Горосорт: - это алгоритм сортировки, представленный в Google Code Jam 2011 года . ^[6] Пока список не упорядочен, подмножество всех элементов переставляется случайным образом. Если это подмножество оптимально выбирается каждый раз, когда это выполняется, ожидаемое значение общего количества раз, когда эта операция должна быть сделана, равно количеству неуместных элементов.
Богобогосорт: - это алгоритм, который был разработан так, чтобы ни в каком значительном списке не добиться успеха до тепловой смерти Вселенной . Он работает, рекурсивно вызывая себя с все меньшими и меньшими копиями начала списка, чтобы увидеть, отсортированы ли они. Базовый вариант - это отдельный элемент, который всегда сортируется. В других случаях он сравнивает последний элемент с максимальным элементом из предыдущих элементов в списке. Если последний элемент больше или равен, он проверяет, соответствует ли порядок копии предыдущей версии, и если да, то возвращается. В противном случае он перетасовывает текущую копию списка и перезапускает рекурсивную проверку. ^[7]
Bozosort: - еще один алгоритм сортировки, основанный на случайных числах. Если список не в порядке, он выбирает два элемента случайным образом и меняет их местами, а затем проверяет, отсортирован ли список. Анализ времени работы бозосорта сложнее, но некоторые оценки можно найти в анализе Х. Грубером «извращенно ужасных» алгоритмов рандомизированной сортировки. ^[1] $O (n!)$ Является ожидаемым средним случаем.
Worstsort: представляет собой алгоритм пессимальной ^[a] сортировки, выполнение которого гарантировано за конечное время; однако не существует вычислимого предела неэффективности алгоритма сортировки, и поэтому он более пессимален, чем другие описанные здесь алгоритмы. $Worstsort$ алгоритм основан на плохой алгоритм сортировки, $badsort$ . Алгоритм плохой сортировки принимает два параметра: $L$ - список, который нужно отсортировать, и $k$ - глубину рекурсии. На рекурсии уровне $к = 0$ , $badsort$ просто использует общий алгоритм сортировки, такие как BubbleSort , сортировать свои входы и возвращает отсортированный список. То есть, $плохая сортировка (L, 0) = пузырьковая сортировка (L)$ . Следовательно, временная сложность плохой сортировки равна $O (n 2),$ если $k = 0$ . Тем не менее, для любого $K > 0$ , $badsort (L, K)$ сначала генерирует $Р$ , список всех перестановок $L$ . Затем $badsort$ вычисляет $badsort (Р, к - 1)$ , и возвращает первый элемент отсортированного $P$ . Чтобы сделать $худший по-$ настоящему пессимальным, $k$ может быть присвоено значение вычислимой возрастающей функции, такой как (например, $f$ $($ $n$ $) =$ $A$ $($ $n$ $,$ $n$ $)$ , где $A$ - функция Аккермана ). Ergo, сортировать список произвольно плохо, вы бы выполнить $worstsort ($ $L$ $,$ $F$ $) = badsort ($ $L$ $,$ $F$ $(длина ($ $L$ $)))$ , где $длина ($ $L$ $)$ есть число элементов в $L$ . Полученный алгоритм имеет сложность , где = факториал $n$ $f\colon \mathbb {N} \to \mathbb {N}$ ${\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}$ $n!^{(m)}=(\dotso ((n!)!)!\dotso )!$ повторяется $m$ раз. Этот алгоритм можно сделать сколь угодно неэффективным, выбрав достаточно быстро растущую функцию $f$ . ^[8]
Slowsort: Другой юмористический алгоритм сортировки, использующий ошибочную стратегию «разделяй и властвуй» для достижения огромной сложности.

Квантовая богосорт [ править ]

Квантовая богосорта - это гипотетический алгоритм сортировки, основанный на богосорте, созданный в шутку компьютерными учеными. Алгоритм генерирует случайную перестановку своих входных данных, проверяет, отсортирован ли список, и, если это не так, уничтожает вселенную. Если предположить, что интерпретация множества миров верна, использование этого алгоритма приведет к существованию ровно одной выжившей вселенной, в которой входные данные успешно отсортированы. ^{[ необходима цитата ]}

См. Также [ править ]

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

Ссылки [ править ]

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

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

Внешние ссылки [ править ]

Реализация алгоритма Викибука имеет страницу по теме: Богосорт

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

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

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

[3] ES Raymond. "бого-сорт". Словарь нового хакера . MIT Press, 1996.

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

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

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

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

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

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

[1]

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