Bogosort

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. května 2021; kontroly vyžadují 5 úprav .

Bogosort  (z amer . comp. slang. bogus - nefunkční, nefunkční, zbytečný) je neefektivní třídicí algoritmus používaný pouze pro vzdělávací účely a na rozdíl od jiných, realističtějších algoritmů.

Pokud se k třídění balíčku karet používá bogosort , musíte nejprve v algoritmu zkontrolovat, zda jsou všechny karty v pořádku, a pokud nejsou, náhodně je zamíchejte, zkontrolujte, zda jsou nyní všechny karty v pořádku a postup opakujte, dokud nebude balíček roztříděn.

Průměrná doba běhu algoritmu

Při iteraci smyčkou jednou za sekundu může seřazení následujícího počtu prvků v průměru trvat:

Počet prvků jeden 2 3 čtyři 5 6 7 osm 9 deset jedenáct 12
Průměrný čas 1 s 4 s 18 s 96 s 10 min 1,2 h 9,8 hod 3,7 dne 37,8 dne 1,15 roku 13,9 let 182 let

Se 4jádrovým procesorem běžícím na frekvenci 2,4 GHz (9,6 miliardy operací za sekundu):

Počet prvků deset jedenáct 12 13 čtrnáct patnáct 16 17 osmnáct 19 dvacet
Průměrný čas 0,0037 s 0,045 s 0,59 s 8,4 s 2,1 min 33,6 min 9,7 hod 7,29 dne 139 dní 7,6 roku 160 let

Balíček 32 karet vytřídí počítač v průměru 2,7⋅10 19  let.

Příklad implementace

#include <utilita> bool správně ( int * arr , int velikost ) { while ( -- velikost > 0 ) if ( arr [ velikost - 1 ] > arr [ velikost ]) vrátit true ; vrátit false ; } void shuffle ( int * arr , int size ) { for ( int i = 0 ; i < velikost ; ++ i ) std :: swap ( arr [ i ], arr [( rand () % velikost )]); } void bogoSort ( int * arr , int size ) { while ( správně ( arr , velikost )) zamíchat ( arr , velikost ); }

Viz také

Odkazy

 Algoritmy řazení
Teorie Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna
Výběr
vložky
fúze
Žádné srovnání
hybridní
jiný
nepraktický