Bogosort
Z Wikipedii
Bogosort to algorytm sortowania, o bardzo dużej złożoności obliczeniowej i wyjątkowo prosty. Polega na ciągłym losowym zamienianiu miejscami elementów tablicy i sprawdzaniu czy tablica jest już posortowana i można już przerwać działanie. Nie używa się go w praktyce, gdyż posortowanie nawet kilkunastu elementów trwa bardzo długo.
Złożoność obliczeniowa: przeciętnie O(n × n!), bez ograniczeń w najgorszym przypadku.
Pseudokod algorytmu:
funkcja bogosort(tablica) dopóki nie jest_posortowana(tablica) tablica := losowa_permutacja(tablica)
W przypadku używania do mieszania elementów tablicy generatora liczb pseudolosowych, algorytm może nigdy nie zakończyć działania.
Algorytm jest niestabilny.