# Bogo Sort (Bogosort, Stupid Sort) visualisieren: mischen, bis es sortiert ist

> Bogo Sort interaktiv: mischt das Array per Fisher-Yates so lange, bis es zufällig sortiert ist. Erwartete Laufzeit O(n · n!), im Worst Case unbeschränkt.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/bogo-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/bogo-sort.md

Joke-Algorithmus, auch Bogosort oder Stupid Sort: solange durchmischen, bis das Array zufällig sortiert ist.

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.

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.

## Häufige Fragen

### Was ist Bogo Sort?

Bogo Sort, auch Bogosort, Stupid Sort oder Permutationssort genannt, mischt das Array zufällig durch und prüft danach, ob es sortiert ist. Ist es das nicht, mischt er erneut. Er gilt als Lehrbeispiel für einen absichtlich ineffizienten Sortieralgorithmus.

### Ist Bogo Sort ein Witz?

Ja, für die Praxis ist er als Witz gemeint und wird nie eingesetzt. In der Lehre zeigt er, wie schnell die Zahl der Anordnungen wächst: Zwölf Elemente lassen sich auf 479.001.600 Arten anordnen, und Bogo Sort probiert im Mittel so viele Anordnungen durch, bis die sortierte darunter ist.

### Was ist der beste Fall von Bogo Sort?

Im besten Fall ist das Array schon sortiert. Dann genügt eine Prüfung mit n − 1 Vergleichen, und Bogo Sort endet ohne einzigen Mischvorgang in O(n).

### Wie lange braucht Bogo Sort im Mittel und im schlechtesten Fall?

Bei n verschiedenen Werten ist jede Anordnung gleich wahrscheinlich, im Mittel sind also n! Mischvorgänge nötig, jeder mit einer Prüfung von bis zu n − 1 Vergleichen. Das ergibt eine erwartete Laufzeit von O(n · n!). Eine obere Grenze gibt es nicht: Dieselbe falsche Anordnung kann beliebig oft wiederkehren, und der Algorithmus endet im schlechtesten Fall nie.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)