Bogosort

Bogosort

Klasa	Sortowanie
Struktura danych	Szyk
Wydajność w najgorszym przypadku	Bez ograniczeń (wersja losowa), O (( n +1)!) (wersja deterministyczna)
Najlepsza wydajność	O ( n )
Średnia wydajność	O (( n +1)!)
Złożoność przestrzeni w najgorszym przypadku	O ( 1 )

W informatyce bogosort (znany również jako sort permutacyjny , sortowanie głupie , slowsort lub bozosort) to algorytm sortowania oparty na paradygmacie generowania i testowania . Funkcja sukcesywnie generuje permutacje swoich danych wejściowych, aż znajdzie takie, które jest posortowane. Nie jest uważany za przydatny do sortowania, ale może być używany do celów edukacyjnych, aby porównać go z bardziej wydajnymi algorytmami.

Istnieją dwie wersje tego algorytmu: wersja deterministyczna, która wylicza wszystkie permutacje, aż trafi na posortowaną, oraz wersja losowa , która losowo permutuje dane wejściowe. Analogią do działania tej drugiej wersji jest sortowanie talii kart poprzez wyrzucanie talii w powietrze, wybieranie losowych kart i powtarzanie tego procesu, aż talia zostanie posortowana. Jego nazwa to kontaminacja słów fałszywy i sortować .

Opis algorytmu

Poniżej znajduje się opis losowego algorytmu w pseudokodzie :

 gdy nie jest  posortowane (pokład): przetasuj (pokład) 

Oto powyższy pseudokod przepisany w Pythonie 3 :

   

   
    
             

   
    
      
        
      from  random  import  shuffle  def  is_sorted  (  data  )  ->  bool  :  """Określ, czy dane są posortowane."""  return  all  (  a  <=  b  for  a  ,  b  in  zip  (  data  ,  data  [  1  :]))  def  bogosort  (  dane  )  ->  list  :  """Przetasuj dane do czasu posortowania."""  while  not  is_sorted  (  dane  ):  losuj  (  dane  )  zwróć  dane 

Ten kod zakłada, że ​​dane to prosta, zmienna struktura danych podobna do tablicy — jak wbudowana lista w Pythonie — której elementy można bez problemu porównywać.

Czas trwania i zakończenie

Eksperymentalne środowisko wykonawcze bogosort

Jeśli wszystkie elementy do sortowania są różne, oczekiwana liczba porównań wykonanych w przeciętnym przypadku przez randomizowane bogosort jest asymptotycznie równoważna ( e − 1) n ! , a oczekiwana liczba zamian w przypadku przeciętnym wynosi ( n − 1) n ! . Oczekiwana liczba zamian rośnie szybciej niż oczekiwana liczba porównań, ponieważ jeśli elementy nie są uporządkowane, zwykle zostanie to odkryte po kilku porównaniach, bez względu na to, ile elementów jest; ale praca związana z tasowaniem kolekcji jest proporcjonalna do jej wielkości. W najgorszym przypadku liczba porównań i zamian jest nieograniczona, z tego samego powodu, dla którego rzucona moneta może wyrzucić orła dowolną liczbę razy z rzędu.

Najlepszy przypadek występuje, gdy podana lista jest już posortowana; w tym przypadku oczekiwana liczba porównań wynosi n − 1 i nie przeprowadza się żadnych zamian.

Dla każdego zbioru o stałym rozmiarze oczekiwany czas działania algorytmu jest skończony z tego samego powodu, z którego wynika twierdzenie o nieskończonej małpie : istnieje pewne prawdopodobieństwo uzyskania właściwej permutacji, więc przy nieograniczonej liczbie prób prawie na pewno w końcu być wybranym.

Powiązane algorytmy

Gorosort

to algorytm sortowania wprowadzony w Google Code Jam w 2011 roku . Dopóki lista nie jest uporządkowana, podzbiór wszystkich elementów jest losowo permutowany. Jeśli ten podzbiór jest wybierany optymalnie za każdym razem, gdy jest to wykonywane, oczekiwana wartość całkowitej liczby operacji, które należy wykonać, jest równa liczbie zagubionych elementów.

Bogobogosort

to algorytm, który został zaprojektowany tak, aby nie odniósł sukcesu przed śmiercią cieplną wszechświata na jakiejkolwiek obszernej liście. Działa poprzez rekurencyjne wywoływanie siebie z coraz mniejszymi kopiami początku listy, aby sprawdzić, czy są one posortowane. Podstawowy przypadek to pojedynczy element, który jest zawsze sortowany. W innych przypadkach porównuje ostatni element z maksymalnym elementem z poprzednich elementów na liście. Jeśli ostatni element jest większy lub równy, sprawdza, czy kolejność kopii jest zgodna z poprzednią wersją, a jeśli tak, to zwraca. W przeciwnym razie przetasowuje bieżącą kopię listy i ponownie uruchamia sprawdzanie rekurencyjne.

Bozosort

to kolejny algorytm sortowania oparty na liczbach losowych. Jeśli lista nie jest uporządkowana, wybiera losowo dwie pozycje i zamienia je miejscami, a następnie sprawdza, czy lista jest posortowana. Analiza czasu działania bozosortu jest trudniejsza, ale niektóre szacunki można znaleźć w analizie „przewrotnie okropnych” losowych algorytmów sortowania przeprowadzonej przez H. Grubera. że O ( n !) jest oczekiwanym przypadkiem średnim.

Worstsort

to pesymalny algorytm sortowania, który gwarantuje zakończenie w skończonym czasie; jednak jego wydajność może być dowolnie zła, w zależności od konfiguracji. najgorszego sortowania jest oparty na złym algorytmie sortowania, badsort . Algorytm badsort akceptuje dwa parametry: L , który jest listą do posortowania, oraz k , który jest głębokością rekurencji. Na poziomie rekurencji k = 0 badsort używa jedynie zwykłego algorytmu sortowania, takiego jak bubblesort , do sortowania danych wejściowych i zwracania posortowanej listy. To znaczy badsort( L , 0) = bubblesort( L ) . Dlatego złożoność czasowa sortowania złego wynosi O ( n ² ), jeśli k = 0 . Jednak dla dowolnego k > 0 , badsort( L , k ) najpierw generuje P , listę wszystkich permutacji L . Następnie badsort oblicza badsort( P , k − 1) i zwraca pierwszy element posortowanego P . Aby najgorsze sortowanie było naprawdę pesymalne, k można przypisać wartości obliczalnej funkcji rosnącej, takiej jak ${\ Displaystyle f \ okrężnica \ mathbb {N} \ do \ mathbb {N}}$ (np. f ​​( n ) = A ( n , n ) , gdzie A jest funkcją Ackermanna ). Ergo, aby arbitralnie źle posortować listę, wykonaj najgorszy sort( L , f ) = badsort( L , f (length( L ))) , gdzie length( L ) to liczba elementów w L . Otrzymany $_ )}$ , gdzie ${\ Displaystyle n! ^ {(m)} = (\ kropka ((n!)!)! \ kropka)!}$ = silnia n powtórzonych m razy. Algorytm ten można uczynić tak nieefektywnym, jak sobie tego życzy, wybierając odpowiednio szybko rosnącą funkcję f .

Slowsort

to inny humorystyczny algorytm sortowania, który wykorzystuje błędną strategię dziel i zwyciężaj, aby osiągnąć ogromną złożoność.

Quantum Bogosort

to hipotetyczny algorytm sortowania oparty na bogosort, stworzony jako żart wśród informatyków. Algorytm generuje losową permutację swoich danych wejściowych za pomocą kwantowego źródła entropii, sprawdza, czy lista jest posortowana, a jeśli nie, niszczy wszechświat. Zakładając, że interpretacja wielu światów , użycie tego algorytmu spowoduje, że co najmniej jeden ocalały wszechświat, w którym dane wejściowe zostały pomyślnie posortowane w czasie O ( n ) .

Sortowanie cudów

to algorytm sortowania, który sprawdza, czy tablica jest posortowana, dopóki nie nastąpi cud . Nieustannie sprawdza tablicę, dopóki nie zostanie posortowana, nigdy nie zmieniając kolejności tablicy. Ponieważ kolejność nigdy nie jest zmieniana, algorytm ma hipotetyczną złożoność czasową O ( ∞ ) , ale nadal może sortować zdarzenia, takie jak cuda lub pojedyncze zdarzenia . Podczas implementacji tego algorytmu należy zachować szczególną ostrożność, ponieważ kompilatory optymalizujące mogą po prostu przekształcić go w pętlę while(true) .

Zobacz też

• Algorytm Las Vegas
• Stooge sort

Linki zewnętrzne

• BogoSort na WikiWikiWeb
• Nieefektywne algorytmy sortowania
• Bogosort : implementacja działająca w systemach typu Unix , podobna do standardowego programu sortowania .
• Bogosort i jmmcg::bogosort : Proste, ale przewrotne implementacje algorytmu bogosort w C++.
• Pakiet Bogosort NPM : implementacja bogosort dla ekosystemu Node.js.
• Max Sherman Bogo-sort jest trochę powolny , czerwiec 2013 r