Bogosort

Bogosort, Dumbsort 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 Datenstrukturen und Algorithmen 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 ${\displaystyle {\mathcal {O}}(n)}$ (angegeben in der Landau-Notation) sofern die angegebene Liste bereits sortiert ist und im schlechtesten Fall ${\displaystyle \Theta (n\cdot n!)}$.^[3] Die Fakultät ${\displaystyle n!}$ ist die Anzahl der möglichen Anordnungen (Permutationen) ${\displaystyle 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 ${\displaystyle (e-1)\cdot n!}$ strebt, wesentlich geringer.^[3] Hierbei bezeichnet ${\displaystyle e}$ die Eulersche Zahl.

In der Realität kann die Laufzeit beliebig lang sein, allerdings sind übermäßig lange Laufzeiten gemäß 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.

Code

Pseudocode

while not sorted(deck):
  shuffle(deck)

Python

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

Java

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;
    }
}

JavaScript

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;
    }
}

C

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);
}

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. (Memento des Originals vom 15. Januar 2014 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/twiki-edlab.cs.umass.edu 12. Juni 2006
3. H. Gruber, M. Holzer und 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 (PDF-Datei; 193 kB).

Weblinks

• Jargon File entry for bogo-sort (englisch)