Bogosort

Rodzaj	Sortowanie
Struktura danych	Tablica
Złożoność
Czasowa	śr. ${\displaystyle \Omega (n\cdot n!)}$[1]
Pamięciowa	${\displaystyle O(n)}$

Bogosort – niestabilny, trywialny w działaniu algorytm sortowania o bardzo dużej złożoności obliczeniowej, oparty na metodzie prób i błędów.

Działanie algorytmu polega na ciągłym losowym ustawianiu sortowanych elementów i sprawdzaniu czy po wymieszaniu elementy są posortowane. Operacje mieszania powtarzane są aż do posortowania elementów. Aby posortować talię kart tym algorytmem należy wyrzucić talię w powietrze, pozbierać z podłogi i sprawdzić czy karty ułożyły się w oczekiwany porządek. Czynność powtarzamy aż do uzyskania oczekiwanego efektu^[2].

Algorytm stosuje się głównie w celach edukacyjnych, aby uzyskać efekt kontrastu przy porównywaniu z innymi algorytmami. Nie jest używany w praktyce – posortowanie kilkunastu elementów może trwać bardzo długo i nie ma pewności, czy w ogóle się zakończy.

Średnia złożoność obliczeniowa wynosi ${\displaystyle \Omega (n\cdot n!)}$^[1]. W przypadku pesymistycznym sortowanie będzie trwać w nieskończoność^[1]. Zajętość pamięci wynosi ${\displaystyle O(n).}$

dopóki nie jest_posortowana(tablica)
 tablica := losowa_permutacja(tablica)

Różnica pomiędzy Bogosortem a Bozosortem jest taka, że ten drugi – w przypadku, gdy elementy nie są jeszcze posortowane – zamienia miejscami dwa dowolne elementy i ponawia sprawdzanie porządku elementów.

To algorytm sortowania, który został stworzony tak, aby nie odniósł sukcesu do śmierci cieplnej wszechświata.

• przykłady implementacji tego algorytmu
• quantum bogodynamics