Bubble-sort

Einführung

Der Bubble Sort ist ein relativ einfacher Sortieralgorithmus. In der Bubble-Phase wird die Eingabe-Liste 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 getauscht. 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 solange 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. Auch werden immer 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 und vorletzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte....

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.

Pseudo Code

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-1
    i=i+1
    falls A an der Stelle i > A an der Stelle i+1 dann
          A tausche i und i+1
    ende falls
  ende wiederhole
 ende wiederhole
ende prozedur