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.
Zastosowanie 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.
Złożoności Średnia złożoność obliczeniowa wynosi . W przypadku pesymistycznym sortowanie będzie trwać w nieskończoność. Zajętość pamięci wynosi
Pseudokod dopóki nie jest_posortowana(tablica) tablica := losowa_permutacja(tablica)
Odmiany Bozo sort 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.
Bogobogo sort To algorytm sortowania, który został stworzony tak, aby nie odniósł sukcesu do śmierci cieplnej wszechświata.
Zobacz też przykłady implementacji tego algorytmu quantum bogodynamics
Przypisy
Kategoria:Algorytmy sortowania