In der Informatik, bogosort (auch dumme Sorte oder slowsort) ist ein besonders unwirksamer auf dem Erzeugen- und Testparadigma gestützter Sortieren-Algorithmus. Es ist für das Sortieren nicht nützlich, aber kann zu Bildungszwecken verwendet werden, um ihm mit anderen realistischeren Algorithmen gegenüberzustellen; es ist auch als ein Beispiel in der Logikprogrammierung verwendet worden. Wenn bogosort verwendet würden, um ein Deck von Karten zu sortieren, würde es aus der Überprüfung bestehen, wenn das Deck in der Ordnung wäre, und wenn es nicht war, das Deck in die Luft werfend, die Karten aufs Geratewohl aufnehmend, und den Prozess wiederholend, bis das Deck sortiert wird. Sein Name kommt aus dem gefälschten Wort.

Beschreibung des Algorithmus

Folgender ist eine Beschreibung des Algorithmus im Pseudocode.

während nicht inOrder (Deck) tun

Schlurfen (Deck);

Laufzeit und Beendigung

Dieser Sortieren-Algorithmus ist probabilistic in der Natur. Wenn alle zu sortierenden Elemente verschieden sind, ist die erwartete Zahl von Vergleichen im durchschnittlichen Fall zu asymptotisch gleichwertig, und die erwartete Zahl des Tausches im durchschnittlichen Fall ist gleich. Die erwartete Zahl des Tausches wächst schneller als die erwartete Zahl von Vergleichen, weil, wenn die Elemente nicht in der Ordnung sind, das gewöhnlich nach nur einigen Vergleichen egal wie viele Elemente entdeckt wird, dort sind, aber die Arbeit, die Sammlung herzuschieben, ist zu seiner Größe proportional. Im Grenzfall ist die Zahl von Vergleichen und Tausch beide aus demselben Grund unbegrenzt, dass eine geworfene Münze auftauchen könnte, führt jede Zahl von Zeiten hintereinander an.

Der beste Fall kommt vor, wenn die Liste bereits, wie gegeben, sortiert wird; in diesem Fall ist die erwartete Zahl von Vergleichen, und kein Tausch wird überhaupt ausgeführt.

Für jede Sammlung der festen Größe ist die erwartete Laufzeit des Algorithmus aus dem ziemlich gleichen Grund begrenzt, dass der unendliche Affe-Lehrsatz hält: Es gibt etwas Wahrscheinlichkeit, die richtige Versetzung so in Anbetracht einer unbegrenzten Zahl von Versuchen zu bekommen, es wird fast sicher schließlich gewählt. Jedoch, wenn ein Pseudozufallszahlengenerator im Platz einer zufälligen Quelle verwendet wird, kann es nie enden, da diese langfristiges zyklisches Verhalten ausstellen.

Zusammenhängende Algorithmen

Sorte von Goro: Ist ein in der Google 2011-Codemarmelade eingeführter Sortieren-Algorithmus. So lange die Liste nicht in der Ordnung ist, wird eine Teilmenge aller Elemente zufällig permutiert. Wenn diese Teilmenge jedes Mal optimal gewählt wird, wenn das durchgeführt wird, ist der erwartete Wert der Gesamtzahl von Zeiten diese Operation muss getan werden, der Zahl von verlegten Elementen gleich.

Kerl-Sorte: Ist ein anderer auf Zufallszahlen gestützter Sortieren-Algorithmus. Wenn die Liste nicht in der Ordnung ist, pickt sie zwei Sachen aufs Geratewohl auf und tauscht sie, dann Kontrollen, um zu sehen, ob die Liste sortiert wird. Die Laufzeit-Analyse der Kerl-Sorte ist schwieriger, aber einige Schätzungen werden in der Analyse von H. Gruber pervers schrecklichen randomized das Sortieren von Algorithmen gefunden. O (n!) wird gefunden, der erwartete durchschnittliche Fall zu sein.

Quant bogosort: Ein im Witz unter einigen Computerwissenschaftlern ist, dass Quant-Computerwissenschaft verwendet werden konnte, um einen bogosort mit einer Zeitkompliziertheit von O (n) effektiv durchzuführen. Es verwendet wahre Quant-Zufälligkeit, um die Liste zufällig zu permutieren. Die Liste wird dann untersucht, und wenn es nicht in der Ordnung ist, wird das Weltall zerstört. Durch die Vielweltinterpretation der Quant-Physik das Quant randomization Laiche (wo N die Zahl von zufälligen Bit ist) werden Weltall und einer von diesen solch sein, dass dieses einzelne Schlurfen die Liste in der sortierten Ordnung erzeugt hatte.

Siehe auch

• Las Vegas Algorithmus
• Stichwortgeber-Sorte

Links

• auf WikiWikiWeb
• Ineffiziente Sorte-Algorithmen
• Bogosort: Eine Durchführung, die auf Unix ähnlichen Systemen läuft, die dem Standardsorte-Programm ähnlich sind.
• Bogosort und jmmcg:: bogosort: Einfach, noch pervers, C ++ Durchführungen des bogosort Algorithmus.