Bogosort

Bogosort (stupid sort, slowsort) je algoritmus, který slouží k demonstraci nejhoršího možného postupu při řazení prvků. Jedná se pouze o teoretický algoritmus, jenž nemá kromě demonstrace samotné žádné praktické uplatnění.

Princip

Princip bogosortu je triviální – v každém svém kroku zkontroluje, jestli vstupní seznam není již seřazený. Pokud je seřazen, tak terminuje. V opačném případě promíchá seznam a vrátí se do prvního kroku.


Kód

function bogosort(array)
    while !ordered(array)
        shuffle(array)

Složitost

Očekávaná složitost bogosortu je O(n \\cdot n!), jelikož existuje právě n! možných permutací vstupního pole.

Bozosort

Příbuzným algoritmem bogosortu je bozosort. Bozosort v každém svém kroku zkontroluje, jestli již seznam není seřazen. Pokud je seřazen, tak terminuje. V opačném případě prohodí dva náhodné prvky a proceduru zopakuje.

Očekávaná složitost Bozosortu je O(n!).

Literatura

  • GRUBER, Hermann, Markus HOLZER a Oliver RUEPP. Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. Dostupné z: http://www.hermann-gruber.com/data/fun07-final.pdf







Doporučujeme

Internet pro vaši firmu na míru