Bogosort - LinkFang.de





Bogosort


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

Bogosort ist ein (randomisierter) Las-Vegas-Algorithmus, daher ist dessen Laufzeit eine Zufallsvariable. Die erwartete Laufzeit ist im besten Fall [math]\mathcal{O}(n)[/math] (angegeben in der Landau-Notation) sofern die angegebene Liste bereits sortiert ist. Im Mittel beträgt die Laufzeit [math]\mathcal{O}(n \cdot n!)[/math].[3] Die Fakultät [math]n![/math] ist die Anzahl der möglichen Anordnungen (Permutationen) [math]n[/math] 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 [math](e-1) \cdot n![/math] strebt, wesentlich geringer.[3] Hierbei bezeichnet [math]e[/math] 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

  1. TU Berlin: Informatik für Elektrotechniker II - Aufgabenblatt 5 (Memento 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. 3,0 3,1 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


Kategorien: Wissenschaftlicher Witz | Sortieralgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bogosort (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.