Bogo Sort
Joke-Algorithmus: solange durchmischen, bis das Array zufällig sortiert ist.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 function bogoSort(a)
2 while not isSorted(a)
3 shuffle(a)
4 return a
5
6 function isSorted(a)
7 for i from 1 to n - 1
8 if a[i - 1] > a[i] return false
9 return true
10
11 function shuffle(a)
12 for i from n - 1 downto 1
13 j = random(0, i)
14 swap a[i], a[j]
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Bogo Sort (auch Stupid Sort, Slow Sort oder Permutationssort) ist ein als Witz gemeinter Sortieralgorithmus, der jeden Lehrbuchsatz über Effizienz auf den Kopf stellt. Die Idee ist simpel: prüfe, ob das Array sortiert ist; wenn nicht, würfle es komplett neu durch (etwa per Fisher-Yates-Shuffle) und prüfe erneut. Wiederhole das so lange, bis durch reines Glück eine sortierte Permutation entsteht. Im Best Case ist das Array schon beim Start sortiert (eine isSorted-Prüfung, O(n)). Im Average Case sind n!/(n − 1) ≈ n!/n Versuche nötig, plus eine Sortier-Prüfung pro Versuch, was zu einer erwarteten Laufzeit von O(n · n!) führt. Der Worst Case ist unbeschränkt: theoretisch kann der Algorithmus nie terminieren, weil dieselbe falsche Permutation beliebig oft wieder auftauchen kann. Speicherbedarf ist O(1) für die Vergleiche; nicht stabil, weil das Shuffle jede Ordnung gleicher Schlüssel zufällig vernichtet. Diese Visualisierung deckelt bei 80 Shuffle-Runden ab, damit der Player nicht ewig läuft.
Komplexität
- Best Case
O(n) - Average Case
O(n · n!) - Worst Case
O(∞) - Zusatz-Speicher
O(1)
Wann verwenden?
Lehrbeispiel für Erwartungswert, Permutationen und Wahrscheinlichkeitsrechnung sowie als Pointe in Algorithmik-Vorlesungen. In der Praxis nie eingesetzt: bereits bei zehn Elementen sind im Mittel rund 3,6 Millionen Shuffles nötig, bei 20 Elementen über 2 Trillionen. Wer Bogo Sort produktiv nutzt, hat einen Bug, eine Wette verloren oder beides.