Bogosort
W artykule przedstawionym poniżej Bogosort zostanie omówiony z różnych perspektyw, w celu zapewnienia kompleksowego spojrzenia na ten temat. Od jego pochodzenia i historii, poprzez jego dzisiejsze znaczenie, po możliwe przyszłe implikacje, ten artykuł ma na celu przedstawienie pełnego spojrzenia na Bogosort. Zostaną przeanalizowane jego różne aspekty, zbadane zostaną różne jego interpretacje i omówione kontrowersje wokół niego. Ponadto zbadane zostaną implikacje, jakie Bogosort ma w różnych kontekstach oraz przedstawione zostaną refleksje i opinie ekspertów w tej dziedzinie. Bez wątpienia ten artykuł będzie miał na celu rzucić światło na Bogosort i jego wpływ na społeczeństwo.
| |
| Rodzaj | |
|---|---|
| Struktura danych |
Tablica |
| Złożoność | |
| Czasowa | |
| Pamięciowa |
|
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ż
Przypisy
- ↑ a b c 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 0302-9743. (ang.).
- ↑ Informacje o algorytmie Bogosort. . (ang.).