Bubblesort: Algorithmus, Beispiel und Laufzeit

Bubblesort ist ein Verfahren, das eine Liste sortiert, indem es Elemente miteinander vergleicht. Du gehst die Liste in einem Durchlauf von links nach rechts durch. In jedem Schritt vergleichst du die aktuelle Zahl mit ihrem rechten Nachbarn. Beim aufsteigenden Sortieren tauschst du die beiden, wenn die linke Zahl größer ist als die rechte. Sonst bleibt alles, wie es ist.

Danach beginnst du wieder links und machst den nächsten Durchlauf. Das wiederholst du, bis die Liste sortiert ist. Wenn du die Vergleiche dokumentieren sollst, schreibst du für jeden Schritt das verglichene Paar auf, ob du getauscht hast und wie die Liste danach aussieht. Bubblesort heißt auch „Sortieren durch Aufsteigen“ oder „Austauschsortieren“. In der Praxis wird es kaum eingesetzt, in der Lehre spielt es aber eine Rolle, weil es als einfach zu erklären und zu demonstrieren gilt.

Nach dem ersten Durchgang ist die größte Zahl immer am Ende. Der Grund: Bei jedem Tausch wandert die größere der beiden Zahlen nach rechts. Hat der Durchlauf die größte Zahl der Liste erreicht, ist sie größer als jeder Nachbar. Sie wird also bei jedem weiteren Schritt nach rechts getauscht, bis sie ganz hinten liegt. Die größeren Elemente steigen so wie Blasen im Wasser nach oben, also ans Ende der Liste. Daher kommt der Name.

Im zweiten Durchlauf passiert dasselbe mit dem Rest. Nach jedem Durchlauf steht an der rechtesten Position das größte Element des jeweils noch unsortierten Rests. Dieses Element ist größer als alles, was links von ihm bleibt, und kleiner als alles, was schon rechts von ihm fertig steht. Mit jeder Runde kommt rechts also ein weiteres Element dazu, das richtig steht. Deshalb muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden: Der übrige Teil enthält keine größeren Elemente mehr. Im Beispiel von eben musst du im zweiten Durchlauf die 78 nicht mehr vergleichen.

Kleine Elemente am Ende wandern dagegen nur langsam nach vorn, große Elemente am Anfang werden schnell nach hinten getauscht.

Es gibt zwei Varianten. Die einfache Variante hat eine feste Zahl von Durchläufen: Bei einer Liste mit n Elementen zählt die äußere Schleife von n bis 2 herunter. Das sind n − 1 Durchläufe, egal ob getauscht wird. Sie nutzt nicht aus, dass in den restlichen Durchläufen nichts mehr getauscht wird, wenn ein Durchlauf ohne Tausch blieb.

Die Variante mit Abbruch merkt sich mit einer Markierung namens „swapped“, ob in einem Durchlauf getauscht wurde. Wurde nicht getauscht, hört sie auf. Beim Beispiel 55, 07, 78, 12, 42 ändert der 3. Durchlauf nichts mehr. Die Variante mit Abbruch hört danach auf, die einfache Variante macht noch den 4. Durchlauf.

Laufzeit bedeutet zunächst die Zeitdauer, die ein Programm braucht. Sekunden hängen aber von Hardware, Betriebssystem und Taktrate ab. Deshalb schätzt man bei Algorithmen nach oben ab, wie viele einfache Operationen (Elementarschritte) nötig sind, abhängig von der Größe n der Eingabe. Dafür schreibt man O(…) in der sogenannten Landau-Notation.

Die einfache Variante vergleicht im ersten Durchlauf n − 1 Paare, dann n − 2 und so weiter bis 1. Zusammen sind das n·(n − 1)/2 Vergleiche, auch bei einer schon sortierten Liste. Bei fünf Zahlen sind es 4 + 3 + 2 + 1 = 10. Bubblesort hat die Laufzeit O(n²). Im schlimmsten Fall und im durchschnittlichen Fall wächst sie quadratisch. Im schlimmsten Fall (umgekehrt sortierte Liste) werden höchstens n·(n − 1)/2 Vertauschungen ausgeführt.

Bei einer schon sortierten Liste geht die Variante mit Abbruch die Liste nur einmal durch und braucht O(n) Schritte. Bei O(n) verdoppelt sich die Ausführungsdauer, wenn doppelt so viele Zahlen eingegeben werden. Sind die Elemente schon nah an ihren Zielpositionen, ist die Laufzeit erheblich besser als O(n²). Für kleine Eingaben kann Bubblesort in Frage kommen. Sonst wird es kaum eingesetzt, weil andere Verfahren ein besseres Laufzeitverhalten haben.