Tekst źródłowy strony Bogosort

{{Algorytm infobox
 |nazwa            = Bogosort
 |grafika          = 
 |wielkość grafiki = 
 |opis grafiki     = 
 |rodzaj           = [[Sortowanie]]
 |struktura        = Tablica
 |czas             = śr. <math>\Omega(n\cdot n!)</math><ref name="fun" />
 |pamięć           = <math>O(n)</math>
}}
'''Bogosort''' – [[niestabilny algorytm sortowania|niestabilny]], trywialny w działaniu [[Sortowanie|algorytm sortowania]] o bardzo dużej [[złożoność obliczeniowa|złożoności obliczeniowej]], oparty na [[Metoda prób i błędów|metodzie prób i błędów]].

Działanie algorytmu polega na ciągłym [[losowość|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<ref>{{cytuj stronę|url=http://www.catb.org/~esr/jargon/html/B/bogo-sort.html|tytuł=Informacje o algorytmie Bogosort|język=en|data dostępu=2009-05-09}}</ref>.

== 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 ==
[[Złożoność oczekiwana|Średnia złożoność obliczeniowa]] wynosi <math>\Omega(n\cdot n!)</math><ref name="fun" />. W [[Złożoność pesymistyczna|przypadku pesymistycznym]] sortowanie będzie trwać w nieskończoność<ref name="fun" />. [[Złożoność obliczeniowa#Złożoność pamięciowa|Zajętość pamięci]] wynosi <math>O(n).</math>

== 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 [[Śmierć cieplna Wszechświata|śmierci cieplnej wszechświata]].

== Zobacz też ==
* [[b:Kody źródłowe/Bogosort|przykłady implementacji tego algorytmu]]
* [[quantum bogodynamics]]

== Przypisy ==
{{Przypisy|
<ref name="fun">{{Cytuj pismo |nazwisko = Gruber |imię = Hermann |nazwisko2 = Holzer |imię2 = Markus |nazwisko3 = Ruepp |imię3 = Oliver |tytuł = Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms |url = http://www.hermann-gruber.com/data/fun07-final.pdf |czasopismo = Lecture Notes in Computer Science |wolumin = 4475 |wydanie = |strony = 183–197 |data = |rok = 2007 |wydawca = Springer Berlin Heidelberg |issn = 0302-9743 |doi = 10.1007/978-3-540-72914-3_17 |język = en}}</ref>
}}

{{Algorytmy sortowania}}

[[Kategoria:Algorytmy sortowania]]