Bubble-sort

Einführung

Der Bubble Sort ist ein relativ einfacher Sortieralgorithmus. In der Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie vertauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da 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 Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt an das Ende der Liste. Es werden jeweils zwei Zahlen miteinander in „Bubbles“ vertauscht.

Beispiel

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich der letzten drei Positionen mehr.

55 07 78 12 42 1. Durchlauf

07 55 78 12 42

07 55 78 12 42

07 55 12 78 42 Letzter Vergleich

07 55 12 42 78 2. Durchlauf

07 55 12 42 78

07 12 55 42 78 Letzter Vergleich

07 12 42 55 78 3. Durchlauf

07 12 42 55 78 Letzter Vergleich

07 12 42 55 78 4. Durchlauf + letzter Vergleich

07 12 42 55 78 Fertig sortiert.

Pseudocode

Der Algorithmus sieht im Pseudocode 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