Bogosort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Bogosort, Monkeysort oder 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]

Laufzeitverhalten[Bearbeiten]

Bogosort ist ein (randomisierter) Las-Vegas-Algorithmus, daher ist dessen Laufzeit eine Zufallsvariable. Die erwartete Laufzeit ist im besten Fall \Theta(n) (angegeben in der Landau-Notation) sofern die angegebene Liste bereits sortiert ist. Im Mittel beträgt die Laufzeit \Theta(n \cdot n!).[3] 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) \cdot n! strebt, wesentlich geringer.[3] Hierbei bezeichnet e die Eulersche Zahl.

In der Realität kann die Laufzeit beliebig lang sein, allerdings sind extrem lange Laufzeiten aufgrund der Markow-Ungleichung auch entsprechend unwahrscheinlich. Der Algorithmus kommt unter der Annahme echter Zufallszahlengeneratoren und einer endlichen Anzahl zu sortierender Elemente fast sicher, d. h. mit Wahrscheinlichkeit 1, nach endlich vielen Schritten zu einem Ergebnis. Das bedeutet, dass es dennoch möglich ist, dass der Algorithmus niemals terminiert. Kommt ein Pseudozufallszahlengenerator zum Einsatz, muss dessen Periode hinreichend lang sein, sodass jede mögliche Permutation mindestens einmal generiert wird, bevor sich die Folge wiederholt.

Einzelnachweise[Bearbeiten]

  1. TU Berlin: Informatik für Elektrotechniker II - Aufgabenblatt 5 (Version vom 13. Juni 2007 im Internet Archive), Sommersemester 2005
  2. University of Massachusetts Amherst: CMPSCI 187 Introduction to Data Structures - Discussion #11: Sorting and Graphs, 12. Juni 2006
  3. a b H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms (PDF-Datei; 193 kB), 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, S. 183-197.

Weblinks[Bearbeiten]