Navigation

 Home
 C und C++
 Exceptionsicherheit
 Programme richtig beenden
 Beliebte Fehler in C/C++
 Was ist volatile?
 Ein dynamisches Array in C
 Sortieralgorithmen in C++
 Bogosort
 Selectionsort
 Insertionsort
 Bubblesort
 Quicksort
 Mergesort
 Heapsort
 Introsort
 Vergleich der Sortieralgorithmen
 Robofight
 Downloads
Bogosort

2. Bogosort

Bogosort wird gemeinhin als Synonym für den schlechtest möglichen Algorithmus benutzt. Da er ein gutes Beispiel dafür ist, zu welchen Grausamkeiten der menschliche Geist ist der Lage ist, habe ich ihn mal in die illustre Runde der Sortieralgorithmen aufgenommen.

2.1. Der Algorithmus

Wir betrachten mit U eine unsortierte Folge von n Elementen, welche in eine sortierte Folge überführt werden soll. Wir prüfen zunächst, ob U bereits sortiert ist. Wenn dies der Fall ist, sind wir direkt fertig. Ansonsten wird U zufällig neu geordnet und erneut geprüft, ob U sortiert ist. Diesen Vorgang wiederholen wir solange, bis wir endlich ein positives Ergebnis erhalten:

1 
2 
3 
4 
5 
6 
7 
algorithm BogoSort(U: Beliebige Folge von Elementen)
    while (U nicht sortiert) 
    do
        Wähle eine neue, zufällige Reihenfolge der Elemente in U;
    end while;
    Ausgabe U;
end algorithm.

Es hängt ein wenig von der Rechenleistung ab, aber wer das Testprogramm zu Bogosort ausprobieren will, sollte es zunächst nur mit Folgen von 6-10 Elementen probieren; wie gleich noch in der Analyse gezeigt wird, terminiert dieser Algorithmus im schlechtesten Fall überhaupt nicht und ist im Durchschnitt unendlich langsam.

2.2. Die Implementierung

Es ist recht günstig, den oben vorgestellten Algorithmus in zwei Teile aufzuteilen: In Zeile 2 des Algorithmus muß geprüft werden, ob U bereits sortiert ist. Diesen Test lagern wir in eine eigenständige Funktion is_sorted aus:

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
template<typename ForwardIterator, typename Predicate>
bool is_sorted(
    ForwardIterator begin,
    ForwardIterator end,
    Predicate predicate) {

    ForwardIterator current = begin;
    ForwardIterator next = begin;

    // Nur bei einer nicht leeren Sequenz ist was zu tun
    if (begin!=end) {

        // Alle Elemente vergleichen
        while(++next!=end) {
            if (predicate(*next, *current)) {
                // Nächstes Element verletzt Sortierkriterium
                return false;
            }
            current = next;
        }
    }

    return true;
}

Nun läßt sich Bogosort wie folgt implementieren:

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
template<typename RandomAccessIterator, typename Predicate>
void bogosort(
    RandomAccessIterator begin, 
    RandomAccessIterator end,
    Predicate predicate) {

    // Zeile 2 vom Algorithmus
    while (!is_sorted(begin, end, predicate)) {
        // Zeile 4 vom Algorithm
        std::random_shuffle(begin, end);
    }
}

Das zufällige Mischen von U wird hier mit der STL Funktion random_shuffle erledigt. Da diese Routine RandomAccessIteratoren benötigt, kann die Implementierung auch nur für diesen Iteratorentypen angewendet werden

2.3. Analyse

2.3.1. Laufzeit

Zunächst muß pro Schleifendurchgang die Funktion is_sorted aufgerufen werden. Ist n die Anzahl der Elemente in U, so beträgt für is_sorted der Aufwand O(n), weil jedes Element aus U mit seinem Nachfolger verglichen werden muß. Für Bogosort bedeutet dies im günstigsten Fall also insgesamt ebenfalls eine Laufzeit von O(n), wobei der günstigste Fall der ist, in dem U bereits sortiert ist. Im ungünstigsten Fall terminiert Bogosort aber nie, weil es ja rein zufälligerweise so sein könnte, daß niemals eine sortierte Reihenfolge zusammengewürfelt wird. Im durchschnittlichen Fall ist zu beachten, daß man n Elemente auf n! verschiedenen Arten anordenen kann. Nimmt man an, daß im Durchschnitt irgendeine beliebige Reihenfolge dieser n! Möglichkeiten die richtige ist, kommt man also auf O(n!) schleifendurchläufen zu O(n) Kosten, so daß im duchschnittlichen Fall Bogosort Kosten von O(nn!) verursacht.

2.3.2. Speicherbedarf

Der Algorithmus ist in situ: die unsortierte Folge wird in situ neu gemischt.

2.3.3. Stabilität

Der Algorithmus ist nicht stabil, denn das Durcheinanderwürfeln der Elemente bringt natürliche jede vorherige Ordnung völlig durcheiander

2.3.4. Vergleich mit anderen Algorithmen

Man muß sich schon anstrengen, einen Algorithmus zu entwicklen, welcher die Aufgabe noch ineffizienter erledigt. Direkt vergleichabr mit anderen hier vorgestellten Algorithmen is Bogosort nicht.