Bogosort - Bogosort

v počítačová věda, Bogosort^[1][2] (také známý jako permutační řazení, hloupý druh,^[3] slowsort,^[4] brokovnice, náhodné řazení, opičí druh, bobosort, Trávník_Gnoome řazení nebo náhodné řazení nebo derp řazení) je vysoce neefektivní třídicí algoritmus založeno na generovat a testovat paradigma. Funkce se postupně generuje obměny svého vstupu, dokud nenajde seřazený. To není užitečné pro třídění, ale může být použito pro vzdělávací účely, aby se porovnalo s efektivnějšími algoritmy.

Existují dvě verze tohoto algoritmu: deterministická verze, která vyjmenuje všechny permutace, dokud nenarazí na seřazenou,^[2][4] a a náhodně verze, která náhodně permutuje jeho vstup. Analogií pro práci druhé verze je třídění a balíček karet vyhozením balíčku do vzduchu, náhodným výběrem karet a opakováním procesu, dokud balíček není tříděn. Jeho jméno je a portmanteau slov falešný a třídit.^[5]

Popis algoritmu

Následuje popis randomizovaného algoritmu v pseudo kód:

zatímco ne isInOrder (balíček): náhodné přehrávání (balíček)

Zde je přepsán výše uvedený pseudokód Python 3:

z náhodný import zamíchatdef is_sorted(data) -> bool:    "" "Zjistit, zda jsou data tříděna." ""    vrátit se Všechno(data[i] <= data[i + 1] pro i v rozsah(len(data) - 1))def Bogosort(data) -> seznam:    "" "Zamíchat data, dokud nebudou tříděna." ""    zatímco ne is_sorted(data):        zamíchat(data)    vrátit se data

Tento kód předpokládá, že data jsou jednoduchým, proměnlivým datovým typem - jako je vestavěný Python seznam—Které prvky lze bez problémů srovnávat.

Zde je příklad zamíchání Standardní ML:

 val _ = zatížení "Náhodný"; zatížení „Int“; val rng = Náhodný.newgen (); zábava vybrat (y :: xs, 0) = (y, xs)   | vybrat (x :: xs, i) = nechat val (y, xs ') = vybrat (xs, i-1) v (y, x :: xs ') konec   | vybrat (_, i) = vyzdvihnout Selhat ("Krátce o" ^ Int.toString i ^ " elementy."); (* Znovu vytvoří seznam v náhodném pořadí odstraněním prvků v náhodných pozicích *) zábava zamíchat xs =    nechat zábava rtake [] _ = []          | rtake ys max =             nechat val (y, ys ') = vybrat (ys, Náhodný.rozsah (0, max) rng)             v y :: rtake ys ' (max-1)             konec    v rtake xs (délka xs) konec; zábava Bogosort xs komp =  nechat zábava je roztříděno (x :: y :: xs) komp = komp(X,y) <> VĚTŠÍ a také je roztříděno (y :: xs) komp       | je roztříděno _ komp = skutečný;     val A = ref xs; v zatímco(ne(je roztříděno (!A) komp)) dělat (  A := zamíchat (!A)  ); (!A) konec;

Provozní doba a ukončení

Experimentální doba běhu bogosortu

Pokud jsou všechny prvky, které mají být tříděny, odlišné, očekávaný počet srovnání provedených v průměrném případě randomizovaným bogosortem je asymptoticky ekvivalentní ${ displaystyle (e-1) n!}$a očekávaný počet swapů v průměrném případě se rovná ${ displaystyle (n-1) n!}$.^[1] Očekávaný počet swapů roste rychleji než očekávaný počet srovnání, protože pokud prvky nejsou v pořádku, bude to obvykle zjištěno po několika srovnáních, bez ohledu na to, kolik prvků existuje; ale práce s mícháním sbírky je úměrná její velikosti. V nejhorším případě je počet srovnání a swapů neomezený, a to ze stejného důvodu, že hodená mince může několikrát za sebou otočit hlavu.

Nejlepší případ nastane, pokud je seznam, jak je uveden, již seřazen; v tomto případě je očekávaný počet srovnání ${ displaystyle n-1}$a nejsou prováděny žádné swapy.^[1]

Pro jakoukoli kolekci pevné velikosti je očekávaná doba chodu algoritmu konečná ze stejného důvodu jako nekonečná věta o opicích platí: existuje určitá pravděpodobnost získání správné permutace, takže vzhledem k neomezenému počtu pokusů bude téměř jistě nakonec být vybrán.

Související algoritmy

Gorosort

je třídicí algoritmus zavedený v roce 2011 Google Code Jam.^[6] Pokud seznam není v pořádku, podmnožina všech prvků je náhodně permutována. Pokud je tato podskupina optimálně vybrána pokaždé, když je provedeno, zobrazí se očekávaná hodnota z celkového počtu případů, kdy je nutné tuto operaci provést, se rovná počtu ztracených prvků.

Bogobogosort

je algoritmus, který byl navržen tak, aby neuspěl před tepelná smrt vesmíru na jakémkoli velkém seznamu. Funguje tak, že se rekurzivně volá s menšími a menšími kopiemi začátku seznamu, aby zjistil, zda jsou seřazeny. Základní případ je jeden prvek, který je vždy seřazen. V ostatních případech porovnává poslední prvek s maximálním prvkem z předchozích prvků v seznamu. Pokud je poslední prvek větší nebo rovný, zkontroluje, zda se pořadí kopie shoduje s předchozí verzí, a pokud ano, vrátí se. Jinak přehraje aktuální kopii seznamu a restartuje její rekurzivní kontrolu.^[7]

Bozosort

je další třídicí algoritmus založený na náhodných číslech. Pokud seznam není v pořádku, vybere náhodně dvě položky a zamění je, poté zkontroluje, zda je seznam seřazen. Analýza doby běhu bozosortu je obtížnější, ale některé odhady lze najít v analýze H. Grubera „zvráceně hrozných“ randomizovaných třídicích algoritmů.^[1] O (n!) Se považuje za očekávaný průměrný případ.

Worstort

je pesimální^[A] třídicí algoritmus, který je zaručeně dokončen v konečném čase; neexistuje však žádné vypočítatelné omezení neúčinnosti třídicího algoritmu, a proto je pesimálnější než jiné zde popsané algoritmy. The ${ displaystyle { text {worstsort}}}$ algoritmus je založen na špatném třídicím algoritmu, ${ displaystyle { text {badsort}}}$. Algoritmus badsort přijímá dva parametry: ${ displaystyle L}$, což je seznam, který se má třídit, a ${ displaystyle k}$, což je hloubka rekurze. Na úrovni rekurze ${ displaystyle k = 0}$, ${ displaystyle { text {badsort}}}$ pouze používá běžný třídicí algoritmus, jako např bubbleort, třídit jeho vstupy a vrátit seřazený seznam. To znamená, ${ displaystyle { text {badsort}} (L, 0) = { text {bubbleort}} (L)}$. Badsortova časová složitost tedy je ${ displaystyle O left (n ^ {2} right)}$ -li ${ displaystyle k = 0}$. Nicméně pro všechny ${ displaystyle k> 0}$, ${ displaystyle { text {badsort}} (L, k)}$ nejprve generuje ${ displaystyle P}$, seznam všech permutací domény ${ displaystyle L}$. Pak, ${ displaystyle { text {badsort}}}$ počítá ${ displaystyle { text {badsort}} (P, k-1)}$, a vrátí první prvek seřazeného ${ displaystyle P}$. Dělat ${ displaystyle { text {worstsort}}}$ opravdu pesimální, ${ displaystyle k}$ lze přiřadit hodnotě vypočítatelné rostoucí funkce, jako je ${ displaystyle f colon mathbb {N} do mathbb {N}}$ (např. ${ displaystyle f (n) = A (n, n)}$, kde ${ displaystyle A}$ je Ackermannova funkce ). Ergo, abys svévolně špatně seřadil seznam, provedl bys ${ displaystyle { text {worstsort}} (L, f) = { text {badsort}} (L, f ({ text {length}} (L)))}$, kde ${ displaystyle { text {length}} (L)}$ = počet prvků v ${ displaystyle L}$. Výsledný algoritmus má složitost ${ displaystyle Omega left ( left (n! ^ {(f (n))} right) ^ {2} right)}$, kde ${ displaystyle n! ^ {(m)} = ( dotso ((n!)!)! dotso)!}$ = faktoriál z ${ displaystyle n}$ iterováno ${ displaystyle m}$ krát. Tento algoritmus lze učinit tak neúčinným, jak si přejeme, výběrem dostatečně rychle rostoucí funkce ${ displaystyle f}$.^[8]

Slowort

Jiný vtipný třídicí algoritmus, který využívá zavádějící strategii rozdělení a dobývání k dosažení obrovské složitosti.

Quantum BogoSort

Quantum BogoSort je ve vtipu o ničeném vesmíru, pokud je algoritmus BogoSort spuštěn na kvantovém počítači a po iteraci není seznam stále seřazen. Ve skutečnosti by se však nic nestalo.

Viz také

• Algoritmus Las Vegas
• Stooge třídění

Reference

externí odkazy

• BogoSort na WikiWikiWeb
• Neúčinné algoritmy řazení
• Bogosort: implementace, která běží dál Unixový systémy podobné standardu třídit program.
• Bogosort a jmmcg :: bogosort^{[trvalý mrtvý odkaz ]}: Jednoduché, ale perverzní C ++ implementace algoritmu bogosort.
• Balíček Bogosort NPM: implementace bogosort pro ekosystém Node.js.
• Max Sherman Bogo-sort je tak trochu pomalý, Červen 2013