Der Bubble-Sort-Algorithmus

1. Einführung

Bubble-Sort ist ein leicht zu implementierender Sortieralgorithmus. Gerade für Programmieranfänger eignet sich dieser Algorithmus für die Umsetzung eines ersten eigenen Sortierprogramms. Diese Simplizität hat allerdings ihren Preis, wie du im Laufe dieses Artikels noch feststellen wirst.

2. Der Algorithmus

Grundsätzlich funktioniert dieser Algorithmus nach dem Prinzip "große Zahlen steigen auf". Daher kommt auch der Name "Bubble-Sort", da die einzelnen Elemente wie Blasen hinaufsteigen. Der Algorithmus arbeitet zudem tauschbasiert, d. h. es werden immer direkt Nachbarn miteinander verglichen und als Prüfkriterium entweder \(\gt\) oder \(\lt\) herangezogen. Betrachten wir zunächst einmal das folgende Beispiel:
\(18\)
\(78\)
\(12\)
\(33\)
\(97\)
Diese Liste an Elementen soll nun der Größe nach sortiert werden. In der Praxis werden dir Listen meistens als horizontal angeordnete Liste von Zahlen begegnen (also in diesem Fall z. B. \(97, 33, 12, 78, 18\)), doch aus Gründen der Anschaulichkeit werden wir dieser Notation ausnahmsweise den Rücken kehren. Schließlich möchtest du ja den namensgebenden Effekt der aufsteigenden Blasen sehen.
Der Algorithmus fußt auf der Idee, dass immer zwei benachbarte (oder hier übereinanderstehende) Elemente miteinander verglichen und im Bedarfsfall vertauscht werden. Vertauscht wird immer dann, wenn das \(i-\)te Element größer als das \((i+1)-\)te Element (also der Nachfolger) ist (sofern wir von einer aufsteigenden Sortierreihenfolge ausgehen). Für das Beispiel der übereinanderstehenden Zahlen bedeutet das, dass immer dann zwei Elemente vertauscht werden, wenn das untere Element größer als das darüberliegende Element ist. Da \(97\) größer als \(33\) ist, werden diese beiden Elemente vertauscht:
\(18\)
\(78\)
\(12\)
\(97\)
\(33\)
Nun wird die \(97\) mit der \(12\) verglichen und du stellst fest, dass hier wieder eine Vertauschung stattfinden muss, da \(97\) größer als das darüberliegende Element \(12\) ist:
\(18\)
\(78\)
\(97\)
\(12\)
\(33\)
Da \(97\gt 78\) ist, wird erneut getauscht:
\(18\)
\(97\)
\(78\)
\(12\)
\(33\)
Du siehst bereits, wie die \(97\) langsam nach oben steigt. Nun findet die letzte Tauschoperation für den ersten Durchlauf des Algorithmus statt, d. h. \(18\) und \(97\) werden vertauscht:
\(97\)
\(18\)
\(78\)
\(12\)
\(33\)
Damit ist die erste Runde des Algorithmus beendet. Nun setzt sich das Spiel mit der \(33\) fort, die allerdings nur mit der \(12\) vertauscht wird:
\(97\)
\(18\)
\(78\)
\(33\)
\(12\)
Da \(33\lt 78\) ist, müssen diese beiden Elemente nicht vertauscht werden. Eine Runde des Algorithmus endet erst, wenn der gesamte nicht sortierte Bereich sortiert wurde. Bereits sortiert wurde bislang nur die \(97\), d. h. es sind noch \(78\) und \(18\) zu untersuchen. Da \(78\gt 18\) ist, werden diese beiden Elemente vertauscht:
\(97\)
\(78\)
\(18\)
\(33\)
\(12\)
Die \(78\) ist nun bis an die Oberfläche aufgestiegen und der sortierte Teil besteht aus \(97\) und \(78\). Jetzt beginnt das Spiel im dritten Durchlauf von vorne. Die \(12\) wird nicht mit der \(33\) vertauscht, da \(12\lt 33\) ist. Da \(33\gt 18\) ist, werden \(33\) und \(18\) vertauscht:
\(97\)
\(78\)
\(33\)
\(18\)
\(12\)
Die Liste ist an dieser Stelle zwar bereits sortiert, doch das weiß der Algorithmus nicht. Dieser läuft so lange weiter, bis alle Elemente aus dem unsortierten Teil der Liste sortiert wurden. Hier sind jetzt nur noch \(18\) und \(12\) unsortiert. Da \(12\lt 18\) ist, findet keine Tauschoperation mehr statt.
Fassen wir diese Vorgehensweise nun noch einmal formal zu dem Bubble-Sort-Algorithmus zusammen:
Algorithmus: Bubble-Sort

Eingabe: (Un-)sortierte Liste \(L\). Zu Beginn wird angenommen, dass alle Elemente noch unsortiert sind. Im Laufe des Algorithmus wird die gesamte Liste in eine sortierte und eine unsortierte Liste zerlegt.
Ausgabe: Sortierte Liste \(L\)
  1. Beginne mit dem ersten Element (i = 0) des unsortierten Teils der Liste.
    • Wenn das erste Element größer als sein nachfolgender Nachbar ist, vertausche die beiden Elemente.
    • Wenn das erste Element kleiner als oder gleich seinem nachfolgenden Nachbar ist, dann führe keine Tauschoperation durch.
  2. Mache mit dem nächsten Element des unsortierten Teils der Liste weiter (i = i + 1).
  3. Wenn du noch nicht am Ende des unsortierten Teils der Liste bist, mache bei Schritt 2 weiter.
  4. Wenn du am Ende des unsortierten Teils der Liste bist, packe das letzte Element in den sortierten Teil der Liste.
  5. Wenn der unsortierte Teil der Liste mehr als ein Element enthält, mache bei Schritt 1 weiter.

3. Beispiel

Betrachten wir nun ein weiteres Beispiel (diesmal mit einer horizontal und nicht vertikal angeordneten Liste). $$99, 22, 9, 6, 28, 30, 17$$ Im ersten Durchgang wandert die \(99\) schrittweise ans rechte Ende der Liste:
\(22, 99, 9, 6, 28, 30, 17\)
\(22, 9, 99, 6, 28, 30, 17\)
\(22, 9, 6, 99, 28, 30, 17\)
\(22, 9, 6, 28, 99, 30, 17\)
\(22, 9, 6, 28, 30, 99, 17\)
\(22, 9, 6, 28, 30, 17, 99\)

Der sortierte Anteil der Liste besteht jetzt aus der \(99\). Der Rest ist immer noch unsortiert. Im zweiten Durchgang wandert die \(22\) schrittweise bis vor die \(28\):
\(9, 22, 6, 28, 30, 17, 99\)
\(9, 6, 22, 28, 30, 17, 99\)

Der Durchgang ist damit aber noch nicht beendet. \(28\) und \(30\) müssen ihre Plätze nicht tauschen, wohl aber \(30\) und \(17\), da \(30\gt 17\) ist:
\(9, 6, 22, 28, 17, 30, 99\)

Jetzt ist der zweite Durchgang beendet und der sortierte Anteil der Liste besteht nun aus \(30\) und \(99\). Im dritten Durchgang tauschen zunächst \(9\) und \(6\) ihre Plätze:
\(6, 9, 22, 28, 17, 30, 99\)

\(9\) und \(22\) müssen nicht vertauscht werden. \(22\) und \(28\) müssen ebenfalls nicht vertauscht werden, wohl aber \(28\) und \(17\), da \(28\gt 17\) ist:
\(6, 9, 22, 17, 28, 30, 99\)

Der sortierte Anteil der Liste besteht jetzt aus \(28, 30\) und \(99\). Im vierten Durchgang muss jetzt nur noch die \(22\) mit der \(17\) getauscht werden:
\(6, 9, 17, 22, 28, 30, 99\)

Jetzt ist die Liste zwar bereits sortiert, doch das weiß der Algorithmus nicht. Da für ihn bislang nur der Teil ab dem Element \(22\) sortiert ist, überprüft er nun in einem fünften Durchgang, ob noch etwas getauscht werden muss. Am Ende des fünften Durchgangs wird die \(17\) dem sortierten Anteil der Liste hinzugefügt, doch an der eigentlichen Liste ändert sich nichts.
\(6, 9, 17, 22, 28, 30, 99\)

Zum Schluss stellt der Algorithmus noch einmal fest, dass \(6\) und \(9\) nicht getauscht werden müssen und der Algorithmus terminiert.

4. Laufzeit

Neben dem Vorteil, dass Bubble-Sort sehr einfach zu verstehen und zu implementieren ist, ist der zusätzliche Speicheraufwand sehr gering, da zum Vertauschen zweier Felder nur ein weiteres Feld notwendig ist. Wenn man den Wert der Variablen \(x\) und \(y\) vertauschen möchte, kann man z. B. den Inhalt von \(x\) in eine weitere Variable \(z\) kopieren, dann den Wert von \(y\) der Variable \(x\) zuweisen und anschließend den zuvor gespeicherten Wert von \(z\) in \(y\) schreiben.
Die Laufzeit des Algorithmus ist allerdings nicht so performant. Um die Laufzeit zu schätzen, kannst du einige Listen mit dem Bubble-Sort sortieren. Wenn man bei einer Liste mit \(n\) Elementen von ca. \(0.5n\) Schritten pro Durchgang ausgeht und man das ganze etwa \(0.5n\) mal machen muss bis alle Elemente sortiert sind, kommt man auf etwa \(0.25n^2\) Tauschoperationen und somit auf die Komplexitätsklasse \(\mathcal{O}(n^2)\). Die Laufzeit des Algorithmus steigt also quadratisch. Bei einer Verdopplung der Anzahl der zu sortierenden Elemente vervierfacht sich der Rechenaufwand. Bei einer Verzehnfachung verhundertfacht sich der Aufwand bereits. Der Algorithmus eignet sich also (wenn überhaupt) nur für eine geringe Anzahl an zu sortierenden Elementen.

5. Aufgabe (mit Lösung)

Gegeben sei die folgende unsortierte Liste an Zahlen: $$24, -8, 22, 18, 7$$ Sortiere diese Liste aufsteigend nach der Größe mithilfe des Bubble-Sort-Algorithmus.
1. Durchgang
\(-8, 24, 22, 18, 7\)
\(-8, 22, 24, 18, 7\)
\(-8, 22, 18, 24, 7\)
\(-8, 22, 18, 7, 24\)

2. Durchgang
\(-8, 18, 22, 7, 24\)
\(-8, 18, 7, 22, 24\)

3. Durchgang
\(-8, 7, 18, 22, 24\)

4. Durchgang
\(-8, 7, 18, 22, 24\)