Randomsort

Der Begriff Bogosortierung oder englisch Bogosort (manchmal auch Stupidsort) bezeichnet ein nicht-stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der Prototyp eines schlechten Algorithmus. Bogosort wird insbesondere in der Informatik-Ausbildung in den Bereichen Algorithmen oder Datenstrukturen verwendet, um an einem Extrembeispiel die Eigenschaften von Sortierverfahren im Allgemeinen zu verdeutlichen.^[1][2] Weiterhin ist Bogosort Bestandteil mehrerer Linux-Distributionen.^[3]

Laufzeitverhalten

Bogosort ist ein (randomisierter) Las-Vegas-Algorithmus, daher ist dessen Laufzeit eine Zufallsvariable. Die erwartete Laufzeit im besten Fall ist, angegeben in der Landau-Notation, $\mathcal{O}(n)$, nämlich wenn die angegebene Liste bereits sortiert ist. Im Mittel beträgt die Laufzeit $\mathcal{O}(n \cdot n!)$.^[4] Die Fakultät n! ist die Anzahl der möglichen Anordnungen (Permutationen) n verschiedener Elemente. Die Operation, die am häufigsten ausgeführt wird, und das Laufzeitverhalten bestimmt, ist die Anzahl der Vertauschungen. Erstaunlicherweise ist die erwartete Anzahl der Vergleiche, die für große Listen gegen $(e-1) \times n!$ strebt, wesentlich geringer.^[4] Hierbei bezeichnet e die Eulersche Zahl.

In der Realität kann die Laufzeit beliebig lange sein, allerdings sind extrem lange Laufzeiten aufgrund der Markow-Ungleichung auch extrem unwahrscheinlich. Der Algorithmus kommt unter der Annahme echter Zufallszahlengeneratoren (fast) immer, d.h. mit Wahrscheinlichkeit 1, nach endlich vielen Schritten zu einem Ergebnis. Kommt hingegen ein Pseudozufallszahlengenerator zum Einsatz, so kann es Eingabemengen geben, bei denen der Algorithmus niemals terminiert.

Einzelnachweise

1. ↑ TU-Berlin: Informatik für Elektrotechniker II - Aufgabenblatt 5, Sommersemester 2005
2. ↑ University of Massachusetts Amherst: CMPSCI 187 Introduction to Data Structures - Discussion #11: Sorting and Graphs, 12. Juni 2006
3. ↑ RPMseek.com: Paketname bogosort
4. ↑ ^{a b} H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, S. 183-197.

Weblinks

• Jargon File entry for bogo-sort (englisch)