Bubblesort

Bubblesort ist der am einfachsten zu beschreibende Sortieralgorithmus: zwei Nachbarn vergleichen, sie tauschen, wenn sie falsch herum stehen, und wiederholen. Bei langen Listen ist er langsam, doch jeder Schritt ist leicht nachzuvollziehen. Deshalb ist er der klassische erste Algorithmus zum Zuschauen.

Balken unterschiedlicher Höhe werden sortiert; zwei Nachbarn sind für einen Tausch hervorgehoben, die höchsten Balken stehen schon am Ende an ihrem Platz
Balken unterschiedlicher Höhe werden sortiert; zwei Nachbarn sind für einen Tausch hervorgehoben, die höchsten Balken stehen schon am Ende an ihrem Platz

Die Idee

Gehen Sie die Liste von links nach rechts durch und betrachten Sie jedes Paar von Nachbarn. Ist der linke Wert größer als der rechte, tauschen Sie sie. Am Ende angekommen, wurde der größte Wert bis auf den letzten Platz getragen, so wie eine Blase an die Oberfläche steigt. Dieser Gang heißt Durchlauf. Wiederholen Sie die Durchläufe, bis die Liste sortiert ist.

Ein Beispiel

Nehmen Sie 5, 1, 4, 2, 8. Der erste Durchlauf vergleicht 5 und 1 und tauscht sie, dann 5 und 4 (Tausch), 5 und 2 (Tausch) sowie 5 und 8 (kein Tausch): 1, 4, 2, 5, 8. Die 8 steht jetzt an ihrem endgültigen Platz. Der zweite Durchlauf vergleicht 1 und 4 (kein Tausch), 4 und 2 (Tausch) sowie 4 und 5 (kein Tausch): 1, 2, 4, 5, 8. Der dritte Durchlauf tauscht nichts mehr, also ist die Liste sortiert: 9 Vergleiche und 4 Vertauschungen.

Warum jeder Durchlauf einen Wert mehr platziert

Während eines Durchlaufs wird der bisher größte Wert immer mitgenommen: Sobald der Durchlauf ihn erreicht, rückt er mit jedem Vergleich einen Platz weiter nach rechts. Der erste Durchlauf setzt also den größten Wert ans Ende, der zweite den zweitgrößten direkt davor und so weiter. Nach Durchlauf k sind die letzten k Plätze endgültig, und der nächste Durchlauf kann einen Platz früher enden. Deshalb werden die Durchläufe kürzer.

Vertauschungen gleich Inversionen

Eine Inversion ist ein Paar von Werten in falscher Reihenfolge: ein größerer Wert irgendwo vor einem kleineren. Das Tauschen zweier Nachbarn in falscher Reihenfolge beseitigt genau eine Inversion und erzeugt keine neue. Bubblesort macht also genau so viele Vertauschungen, wie die Startliste Inversionen hat, egal in welcher Reihenfolge die Vergleiche kommen. Eine sortierte Liste hat keine; eine umgekehrte Liste mit n Werten hat n(n − 1)/2, die größtmögliche Zahl.

Der frühe Abbruch und der Aufwand

Wenn ein ganzer Durchlauf nichts tauscht, stehen alle Nachbarn in der richtigen Reihenfolge, und die Liste ist sortiert. Mit dieser Prüfung erledigt Bubblesort eine sortierte Liste in einem einzigen Durchlauf mit n − 1 Vergleichen. Im schlimmsten Fall braucht es trotzdem n − 1 Durchläufe und n(n − 1)/2 Vergleiche, und im Mittel sind es n(n − 1)/4 Vertauschungen. Beides wächst mit n², eine doppelt so lange Liste dauert also etwa viermal so lange.

Bubblesort ist stabil: Gleiche Werte werden nie getauscht und behalten ihre Reihenfolge. Es sortiert an Ort und Stelle ohne zusätzlichen Speicher. Insertionsort hat dieselben Eigenschaften und braucht meist weniger Schritte, und Mergesort und Quicksort brauchen Zeit proportional zu n log n, was bei langen Listen viel weniger ist.

Ausprobieren

Öffnen Sie die App und drücken Sie „Abspielen“, oder drücken Sie „Schritt“, um einen Vergleich nach dem anderen zu sehen. Die beiden verglichenen Werte sind hervorgehoben, ein Tausch erscheint in eigener Farbe, und Werte, die schon an ihrem Platz stehen, werden grün. Probieren Sie eine umgekehrte Liste für den schlimmsten Fall, eine fast sortierte, um zu sehen, wie der frühe Abbruch die Sortierung nach wenigen Durchläufen beendet, oder geben Sie die Zahlen aus dem Beispiel oben ein.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Bubblesort?

O(n²) im schlimmsten und im mittleren Fall: bis zu n(n − 1)/2 Vergleiche bei n Werten. Mit frühem Abbruch braucht eine bereits sortierte Liste O(n), also einen einzigen Durchlauf. Zusätzlicher Speicher wird nur O(1) benötigt.

Ist Bubblesort stabil?

Ja. Es tauscht zwei Nachbarn nur, wenn der linke echt größer ist. Gleiche Werte überholen sich also nie und behalten ihre ursprüngliche Reihenfolge.

Was ist der Unterschied zwischen Bubblesort und Insertionsort?

Beide tauschen Nachbarn, und beide machen so viele Vertauschungen, wie es Inversionen gibt. Bubblesort macht volle Durchläufe über den unsortierten Teil; Insertionsort schiebt jeden neuen Wert nur so weit zurück wie nötig und macht daher meist weniger Vergleiche, vor allem bei fast sortierten Listen.

Wann ist Bubblesort eine gute Wahl?

Vor allem im Unterricht und bei sehr kurzen Listen, wo Einfachheit wichtiger ist als Tempo. Für alles Größere ist die eingebaute Sortierfunktion Ihrer Programmiersprache viel schneller.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Bubblesort ausprobieren