imported>Duschgeldrache2: Archivlink geprüft

2026-02-20T20:51:51Z

Archivlink geprüft

Neue Seite

'''Bogosort''', '''Pogosort''', '''Dumbsort''' oder '''Stupidsort''' (auch '''Omarsort''') bezeichnet ein nicht-[[Stabilität (Sortierverfahren)|stabiles]] [[Sortierverfahren]], bei dem die Elemente so lange [[Zufällige Permutation|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 [[Datenstruktur]]en und Algorithmen verwendet, um an einem Extrembeispiel die Eigenschaften von Sortierverfahren im Allgemeinen zu verdeutlichen.<ref>[[TU Berlin]]: {{Webarchiv | url=http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf| wayback=20070613075034|text= Informatik für Elektrotechniker II – Aufgabenblatt 5}}, Sommersemester 2005</ref><ref>[[University of Massachusetts Amherst]]: ''{{Webarchiv|url=http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf |wayback=20140115051946 |text=CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. }}'' 12. Juni 2006</ref>

== Laufzeitverhalten ==
Bogosort ist ein (randomisierter) [[Las-Vegas-Algorithmus]], daher ist dessen [[Laufzeit (Informatik)|Laufzeit]] eine [[Zufallsvariable]]. Die [[Erwartungswert|erwartete]] Laufzeit ist im besten Fall <math>\mathcal{O}(n)</math> (angegeben in der [[Landau-Symbole|Landau-Notation]]) sofern die angegebene Liste bereits sortiert ist und im schlechtesten Fall <math>\Theta(n \cdot n!)</math>.<ref name="Fun07">H. Gruber, M. Holzer und O. Ruepp: ''[http://www.hermann-gruber.com/pdf/fun07-final.html 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 (PDF; 193 kB).</ref> Die [[Fakultät (Mathematik)|Fakultät]] <math>n!</math> ist die Anzahl der möglichen Anordnungen ([[Permutation]]en) <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.<ref name="Fun07"/> Hierbei bezeichnet <math>e</math> die [[Eulersche Zahl]].

In der Realität kann die Laufzeit beliebig lang sein, allerdings sind übermäßig lange Laufzeiten gemäß der [[Markow-Ungleichung (Stochastik)|Markow-Ungleichung]] auch entsprechend unwahrscheinlich. Der Algorithmus kommt unter der Annahme echter [[Zufallszahlengenerator]]en und einer endlichen Anzahl zu sortierender Elemente [[Fast sichere Eigenschaften|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.

== Code ==
=== Pseudocode ===
<syntaxhighlight lang="pascal" line="1">
while not sorted(deck):
shuffle(deck)
</syntaxhighlight>

=== Python ===
<syntaxhighlight lang="python" line="1">
from random import shuffle

def bogosort(data: list) -> list:
while not all(a <= b for a, b in zip(data, data[1:])):
shuffle(data)
return data
</syntaxhighlight>

=== Java ===
<syntaxhighlight lang="java" line="1">
class Main {
public static int[] sort(int[] toSort) {
Random r = new Random();

while (!isSorted(toSort)) { // Prüfen, ob sortiert
int a = r.nextInt(toSort.length);
int b = r.nextInt(toSort.length);

int temp = toSort[a];
toSort[a] = toSort[b];
toSort[b] = temp;
}
return toSort;
}
static boolean isSorted(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
}
</syntaxhighlight>

=== JavaScript ===
<syntaxhighlight lang="javascript" line="1">
function sort(arr) {
while(!isSorted()) {
var a = Math.floor(Math.random() * arr.length);
var b = Math.floor(Math.random() * arr.length);
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

function isSorted() {
for(var i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
}
</syntaxhighlight>

=== C ===
<syntaxhighlight lang="c" line="1">
inline void swap(register int *a, register int *b) {
register int temp = *a;
*a = *b;
*b = temp;
}

int isSorted(int arr[], size_t n) {
for (size_t i = 0; i < n - 1; ++i)
if (arr[i] > arr[i + 1])
return 0;

return 1;
}

void shuffle(int arr[], size_t n) {
for (size_t i = n - 1; i > 0; --i) {
int j = rand() % (i + 1);
swap(&arr[i], &arr[j]);
}
}

void bogoSort(int arr[], size_t n) {
while (!isSorted(arr, n))
shuffle(arr, n);
}

</syntaxhighlight>

== Einzelnachweise ==
<references />

== Weblinks ==
* [http://www.catb.org/jargon/html/B/bogo-sort.html Jargon File entry for ''bogo-sort''] (englisch)

[[Kategorie:Sortieralgorithmus]]
[[Kategorie:Wissenschaftlicher Witz]]

Bogosort - Versionsgeschichte

imported>Duschgeldrache2: Archivlink geprüft