Богосорт

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

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

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

Псевдокод

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

пока не отсортировано(колода): тасовать(колоду)

С

Реализация на языке C :

#include <stdio.h> #include <stdlib.h> #include <время.h> // выполняет сортировку bogo на месте для заданного массиваstatic void bogo_sort ( int * a , int size );     // возвращает 1, если данный массив отсортирован, и 0 в противном случаеstatic int is_sorted ( int * a , int size );     // перемешивает заданный массив в случайном порядкестатическая пустота перетасовка ( int * a , int size );     void bogo_sort ( int * a , int size ) {      в то время как ( ! is_sorted ( a , size )) {    перетасовать ( а , размер );  }}int is_sorted ( int * a , int size ) {      для ( int i = 0 ; i < размер -1 ; i ++ ) {          если ( а [ я ] > а [ я + 1 ]) {     вернуть 0 ;  } } возврат 1 ; }недействительный shuffle ( int * a , int size ) {      int temp , случайное ;   для ( int i = 0 ; i < размер ; i ++ ) {          случайный = ( int ) (( double ) rand () / (( double ) RAND_MAX + 1 ) * размер );            temp = a [ случайное ];   а [ случайный ] = а [ я ];   а [ я ] = темп ;   }}инт мейн () {   // пример использования int вход [] = { 68 , 14 , 78 , 98 , 67 , 89 , 45 , 90 , 87 , 78 , 65 , 74 };                 размер int = sizeof ( вход ) / sizeof ( * вход );      // инициализируем генератор псевдослучайных чисел srand ( время ( NULL )); bogo_sort ( вход , размер );  // отсортированный результат: 14 45 65 67 68 74 78 78 87 89 90 98 printf ( "отсортированный результат:" ); для ( int i = 0 ; i < размер ; i ++ ) {          printf ( "%d" , input [ i ]);  } printf ( " \n " ); вернуть 0 ; }

Питон

Реализация на Python 3 :

импорт  случайный# эта функция проверяет, отсортирован ли массив def  is_sorted ( random_array ):  for  i  in  range ( 1 ,  len ( random_array )):  if  random_array [ i ]  <  random_array [ i  -  1 ]:  return  False  return  True# эта функция многократно перемешивает элементы массива, пока они не будут отсортированы def bogo_sort (  random_array ) : while  not  is_sorted  ( random_array ) :  random.shuffle ( random_array ) return random_array  # эта функция генерирует массив со случайно выбранными целочисленными значениями def  generate_random_array ( size ,  min_val ,  max_val ) :  return  [ random.randint ( min_val , max_val ) for _ in range ( size ) ]     # размер, минимальное значение и максимальное значение случайно сгенерированного массива size  =  10 min_val  =  1 max_val  =  100 random_array  =  generate_random_array ( size ,  min_val ,  max_val ) print ( "Несортированный массив:" ,  random_array ) sorted_arr  =  bogo_sort ( random_array ) print ( "Сортированный массив:" ,  sorted_arr )

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

Продолжительность и окончание действия

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

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

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

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

Горосорт: Алгоритм сортировки, представленный на Google Code Jam 2011 года . ^[6] Пока список не упорядочен, подмножество всех элементов случайным образом переставляется. Если это подмножество оптимально выбирается каждый раз, когда это выполняется, ожидаемое значение общего числа раз, которое необходимо выполнить эту операцию, равно числу неправильно размещенных элементов.
Bogobogosort: Алгоритм, который рекурсивно вызывает себя с меньшими и меньшими копиями начала списка, чтобы проверить, отсортированы ли они. Базовый случай — один элемент, который всегда отсортирован. В других случаях он сравнивает последний элемент с максимальным элементом из предыдущих элементов в списке. Если последний элемент больше или равен, он проверяет, соответствует ли порядок копии предыдущей версии, и если да, то возвращается. В противном случае он перетасовывает текущую копию списка и перезапускает свою рекурсивную проверку. ^[7]
Бозосорт: Другой алгоритм сортировки, основанный на случайных числах. Если список не упорядочен, он выбирает два элемента наугад и меняет их местами, затем проверяет, отсортирован ли список. Анализ времени выполнения bozosort сложнее, но некоторые оценки можно найти в анализе Х. Грубера «извращенно ужасных» рандомизированных алгоритмов сортировки. ^[1] $O(n!)$ оказывается ожидаемым средним случаем.
Худший сорт: Алгоритм пессимальной сортировки, который гарантированно завершается за конечное время; однако его эффективность может быть произвольно плохой, в зависимости от его конфигурации. Алгоритм $худшей сортировки$ основан на плохом алгоритме сортировки, $badsort$ . Алгоритм плохой сортировки принимает два параметра: $L$ , который является списком для сортировки, и $k$ , который является глубиной рекурсии. На уровне рекурсии $k = 0$ , $badsort$ просто использует общий алгоритм сортировки, такой как bubblesort , для сортировки своих входных данных и возврата отсортированного списка. То есть, $badsort(L, 0) = bubblesort(L)$ . Следовательно, временная сложность badsort составляет $O(n 2),$ если $k = 0$ . Однако для любого $k > 0$ , $badsort(L, k)$ сначала генерирует $P$ , список всех перестановок $L$ . Затем $badsort$ вычисляет $badsort(P, k - 1)$ и возвращает первый элемент отсортированного $P$ . Чтобы сделать $worstsort$ действительно пессимальной, $k$ можно присвоить значению вычислимой возрастающей функции, такой как (например, $f$ $($ $n$ $) =$ $A$ $($ $n$ $,$ $n$ $)$ , где $A$ — функция Аккермана ). Таким образом, чтобы отсортировать список произвольно плохо, можно выполнить $worstsort($ $L$ $,$ $f$ $) = badsort($ $L$ $,$ $f$ $(length($ $L$ $)))$ , где $length($ $L$ $)$ — количество элементов в $L$ . Полученный алгоритм имеет сложность , где = факториал $n ,$ повторенный $m$ раз. Этот алгоритм можно сделать настолько неэффективным, насколько это необходимо, выбрав достаточно быстро растущую функцию $f$ . ^[8] $f\двоеточие \mathbb {N} \to \mathbb {N}$ ${\textstyle \Омега \left(\left(n!^{(f(n))}\right)^{2}\right)}$ $n!^{(m)}=(\dotso ((n!)!)!\dotso )!$
Медленная сортировка: Другой юмористический алгоритм сортировки, использующий ошибочную стратегию «разделяй и властвуй» для достижения огромной сложности.
Квантовая сортировка богов: Гипотетический алгоритм сортировки, основанный на bogosort, созданный в качестве шутки среди компьютерных ученых. Алгоритм генерирует случайную перестановку своих входных данных с использованием квантового источника энтропии, проверяет, отсортирован ли список, и, если нет, уничтожает вселенную. Предполагая, что многомировая интерпретация верна, использование этого алгоритма приведет к по крайней мере одной выжившей вселенной, где входные данные были успешно отсортированы за время $O(n)$ . ^[9]
Чудо сортировка: Алгоритм сортировки, который проверяет, отсортирован ли массив, пока не произойдет чудо . Он постоянно проверяет массив, пока он не будет отсортирован, никогда не меняя порядок массива. ^[10] Поскольку порядок никогда не изменяется, алгоритм имеет гипотетическую временную сложность $O (\infty)$ , но он все еще может сортировать события, такие как чудеса или единичные сбои . Особую осторожность следует проявлять при реализации этого алгоритма, поскольку оптимизирующие компиляторы могут просто преобразовать его в цикл while(true) . Однако наилучшим случаем является $O (n)$ , что происходит в отсортированном списке. Поскольку он делает только сравнения, он и строго на месте, и стабилен.
сортировать бозобого: Алгоритм сортировки, который работает только в том случае, если список уже упорядочен, в противном случае применяются условия чудесной сортировки.
Божественный сорт: Алгоритм сортировки, который берет список и решает, что поскольку существует такая низкая вероятность того, что список случайно появился в своей текущей перестановке (вероятность 1/n!, где n — количество элементов), должна быть причина для порядка списка. Следовательно, его следует считать отсортированным способом, которого мы не понимаем, и у нас нет никаких прав сортировать его в соответствии с нашими убеждениями, как если бы он был отсортирован «так, как задумал Бог». Также известна как сортировка по методу интеллектуального замысла. ^[11]

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

Ссылки

^ abcdef Грубер, Х.; Хольцер, М.; Рюпп, О. (2007), «Сортировка медленным способом: анализ извращенно ужасных рандомизированных алгоритмов сортировки», 4-я Международная конференция по развлечениям с алгоритмами, Кастильончелло, Италия, 2007 (PDF) , Lecture Notes in Computer Science, т. 4475, Springer-Verlag, стр. 183–197, doi :10.1007/978-3-540-72914-3_17, ISBN 978-3-540-72913-6.
^ ab Киселёв, Олег; Шан, Чунг-Чи; Фридман, Дэниел П.; Сабри, Амр (2005), "Backtracking, interleaving, and termifying monad transformers: (functional pearl)", Труды Десятой международной конференции ACM SIGPLAN по функциональному программированию (ICFP '05) (PDF) , SIGPLAN Notices, стр. 192–203, doi :10.1145/1086365.1086390, S2CID 1435535, архивировано из оригинала (PDF) 26 марта 2012 г. , извлечено 22 июня 2011 г.
^ ES Raymond. "bogo-sort". Новый хакерский словарь . MIT Press, 1996.
^ Naish, Lee (1986), «Отрицание и квантификаторы в NU-Prolog», Труды Третьей международной конференции по логическому программированию , Lecture Notes in Computer Science , т. 225, Springer-Verlag, стр. 624–634, doi :10.1007/3-540-16492-8_111, ISBN 978-3-540-16492-0.
^ "bogosort". xlinux.nist.gov . Получено 11 ноября 2020 г. .
^ Google Code Jam 2011, Квалификационные раунды, Задача D
^ Богобогосорт
^ Лерма, Мигель А. (2014). «Насколько неэффективным может быть алгоритм сортировки?». arXiv : 1406.1077 [cs.DS].
^ The Other Tree (23 октября 2009 г.). «Quantum Bogosort» (PDF) . MathNEWS . 111 (3): 13. Архивировано (PDF) из оригинала 5 июля 2020 г. . Получено 20 марта 2022 г. .
^ "Miracle Sort". The Computer Science Handbook . Получено 9 сентября 2022 г.
^ "Intelligent Design Sort". www.dangermouse.net . Получено 6 ноября 2024 г. .

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

В Wikibook Algorithm Implementation есть страница по теме: Bogosort

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