Stupid sort
Stupid sort (také Bogo sort, bozo sort, blort sort, monkey sort, random sort nebo drunk man sort) je velmi neefektivní třídicí algoritmus. Používá se jenom k výukovým účelům ke srovnání s reálnějšími algoritmy z hlediska porovnávání. Funguje tak, že se postupně (deterministicky nebo náhodně, podle typu algoritmu) generují permutace vstupní množiny, a pokud se ukáže, že vygenerovaná permutace dává správné seřazení vstupní množiny, algoritmus skončí.
Časová složitost a konečnost[editovat | editovat zdroj]
Tento třídicí algoritmus je z podstaty pravděpodobnostní. Pokud jsou všechny řazené prvky navzájem různé, očekávaný počet srovnání v nejhorším a průměrném případě je asymptoticky ekvivalentní (e - 1)n! a očekávaný počet prohození prvků (n - 1)n!. V nejlepším případě jsou zadané prvky seřazené, v tom případě je počet srovnání roven n - 1 a prohození není žádné. Přesná průměrná složitost závisí na tom, kolik je v množině různých hodnot, kolikrát se v ní vyskytují, ale v netriviálních případech se dá očekávat superexponenciální růst v n (n!). Algoritmus skončí ze stejného důvodu jako infinite monkey theorem. Existuje nenulová pravděpodobnost získání správné permutace prvků, takže při neomezeném počtu pokusů se musí vyskytnout.
Související algoritmy[editovat | editovat zdroj]
Bozo sort[editovat | editovat zdroj]
Bozo sort je další algoritmus založený na náhodných číslech. Pokud není množina seřazená, vyberou se náhodně dva prvky a prohodí se.
Kvantový stupid sort[editovat | editovat zdroj]
Podle vtipu některých informatiků by se kvantový počítač dal použít pro efektivní implementaci stupid sortu s časovou složitostí O(n). Používá kvantovou nahodilost, aby náhodně permutoval prvky. Podle interpretace mnoha světů kvantové fyziky vytvoří kvantová nahodilost nekonečný počet vesmírů, z nichž v některých bude posloupnost po prvním kroku správně seřazená, protože celkový počet různých pořadí je sice velký, nicméně konečný. Posloupnost je pak otestována, jestli je seřazená (to vyžaduje n - 1 porovnání); pokud nejsou ve správném pořadí, počítač vyvolá operaci „znič vesmír“. Pouze ve vesmírech, které zůstaly, budou pozorovatelé, kteří uvidí, že randomizace fungovala na první pokus a že je posloupnost seřazená.
Kvantový algoritmus potřebuje O(n.log n) bitů kvantové nahodilosti.
Je třeba dát pozor při výběru algoritmu pro implementaci kvantovým počítačem. Například je velmi nepravděpodobné, že výše zmíněný bozo sort uspěje po jedné iteraci a pro většinu vstupů (ty, v nichž je ve špatném pořadí víc než jeden pár prvků) po jedné iteraci uspět nemůže. Pro takovéto vstupy by pozorovatelé sledovali záhadná selhání nebo nepravděpodobné nehody, které by bránily počítači v práci, protože všechny vesmíry, v nichž operoval, jsou zničeny.