Bogosort

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] 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 Θ(n), angegeben in der Landau-Notation, wenn die angegebene Liste bereits sortiert ist. Im Mittel beträgt die Laufzeit \Theta(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 sicher, 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


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω …   Wikipedia

  • Bogosort — (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort… …   Википедия

  • 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 …   Deutsch Wikipedia

  • Stupidsort — 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 …   Deutsch Wikipedia

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”