Bogosort

Bogosort
Rodzaj	Sortowanie
Struktura danych	Tablica
Złożoność
Czasowa	О(n*n!)
Pamięciowa	O(n)

Bogosort – niestabilny, trywialny w działaniu algorytm sortowania o bardzo dużej złożoności obliczeniowej.

Zasada działania

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 wynośi O(n*n!). W przypadku pesymistycznym sortowanie będzie trwać w nieskończoność. Zajętość pamięci wynosi O(n).

Pseudokod

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

Implementacja

Zobacz przykłady implementacji tego algorytmu na stronie Wikiźródeł

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.

Zobacz także

• Quantum bogodynamics