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 , jelikož existuje právě 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 .

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