Bubblesort

Einführung

Der Bubble Sort (Sortieren durch Aufsteigen) ist ein verhältnismäßig einfacher Sortieralgorithmus. In der sogenannten Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuell betrachtete Element mit seinem rechten Nachbarn verglichen. Falls die beiden Elemente das vorgegebene Sortierkriterium verletzen (z. B. das linke größer als das rechte ist), werden sie vertauscht. Am Ende einer solchen Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe fest am Ende der Liste.

Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das jeweils letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es bereits seine finale Position erreicht hat und die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Luftblasen im Wasser (daher der Name Bubble) Schritt für Schritt immer weiter nach oben an das Ende der Liste. Es werden stets zwei benachbarte Zahlen miteinander in „Bubbles“ verglichen und bei Bedarf vertauscht.

Beispiel

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett und kursiv markierten Zahlen werden jeweils miteinander verglichen. Ist die linke Zahl größer als die rechte, so werden beide vertauscht. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts an die letzte Position. Im zweiten Durchlauf muss diese letzte Position folglich nicht mehr verglichen werden. Im dritten Durchlauf entfallen die letzten zwei Positionen, und so weiter.

1. Durchlauf

• 55 07 78 12 42 (55 ist größer als 07 -> Tausch)
• 07 55 78 12 42 (55 ist nicht größer als 78 -> kein Tausch)
• 07 55 78 12 42 (78 ist größer als 12 -> Tausch)
• 07 55 12 78 42 (78 ist größer als 42 -> Tausch, letzter Vergleich)

2. Durchlauf (78 ist bereits fest positioniert)

• 07 55 12 42 78
• 07 55 12 42 78 (Tausch)
• 07 12 55 42 78 (Tausch, letzter Vergleich)

3. Durchlauf (55 und 78 sind fest positioniert)

• 07 12 42 55 78
• 07 12 42 55 78 (Letzter Vergleich)

4. Durchlauf

• 07 12 42 55 78 (Letzter Vergleich)

07 12 42 55 78 – Die Liste ist fertig sortiert.

Pseudocode

Der Algorithmus sieht im Pseudocode der unoptimierten Basisvariante so aus:

prozedur bubbleSort(A ist Liste sortierbarer Elemente)
    n = Länge von A
    wiederhole solange n > 1
        n = n - 1
        i = 0
        wiederhole solange i < n
            falls A[i] > A[i + 1] dann
                tausche A[i] und A[i + 1]
            ende falls
            i = i + 1
        ende wiederhole
    ende wiederhole
ende prozedur

Komplexität

Mit Hilfe der Laufzeitanalyse betrachten wir nun die Zeitkomplexität des Algorithmus Bubble Sort für ein Array der Länge [math]\displaystyle{ n }[/math].

Best Case

Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist.

• Unoptimierte Variante (siehe Pseudocode): Auch wenn keine Vertauschungen notwendig sind, durchläuft der oben notierte Algorithmus die Liste strikt weiter. Er führt [math]\displaystyle{ \frac{n(n - 1)}{2} }[/math] Vergleiche aus. Die Zeitkomplexität liegt hier also bei [math]\displaystyle{ O(n^2) }[/math].
• Optimierte Variante (Praxis-Standard): In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag `wurdeGetauscht`) implementiert. Findet in einem kompletten Durchlauf kein einziger Tausch statt, weiß der Algorithmus, dass die Liste sortiert ist, und bricht vorzeitig ab. In dieser optimierten Form benötigt er im Best Case nur [math]\displaystyle{ n - 1 }[/math] Vergleiche. Die Zeitkomplexität sinkt dadurch auf eine lineare Laufzeit von [math]\displaystyle{ O(n) }[/math].

Average Case

Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor. Etwa die Hälfte der maximal möglichen Vertauschungen muss durchgeführt werden. Sowohl die Anzahl der Vergleiche als auch die der Vertauschungen wachsen quadratisch zur Eingabemenge [math]\displaystyle{ n }[/math]. Konstante Faktoren (wie die Halbierung der Tauschoperationen) werden in der Landau-Notation ignoriert. Die Zeitkomplexität im Average Case liegt somit bei [math]\displaystyle{ O(n^2) }[/math].

Worst Case

Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist. In diesem Fall ist das aktuell betrachtete Element immer größer als sein rechter Nachbar. Der Algorithmus muss in jedem einzelnen Schritt eine Vertauschung durchführen, da jedes Element an das andere Ende der Liste "blubbern" muss. Er führt die maximale Anzahl an Vergleichen und Vertauschungen durch: [math]\displaystyle{ \frac{n(n - 1)}{2} }[/math]. Da der Term mit der höchsten Potenz das Wachstum dominiert, liegt die Komplexitätsklasse des Bubble Sorts im Worst Case bei [math]\displaystyle{ O(n^2) }[/math].