Bogosort

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Bogosort
Rodzaj Sortowanie
Struktura danych Tablica
Złożoność
Czasowa śr. O((n-1)!)[1]
Pamięciowa O(n)

Bogosortniestabilny, 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].

Zastosowanie[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Pseudokod[edytuj | edytuj kod]

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

Odmiany[edytuj | edytuj kod]

Bozo sort[edytuj | edytuj kod]

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 też[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 1,2 Hermann Gruber, Markus Holzer, Oliver Ruepp. Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. „Lecture Notes in Computer Science”. 4475, s. 183–197, 2007. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-72914-3_17. ISSN 03029743 (ang.). 
  2. Informacje o algorytmie Bogosort (ang.). [dostęp 2009-05-09].