Mit Google fortfahren
Bubblesort: Algorithmus, Beispiel und Laufzeit
Bubblesort sortiert eine Liste, indem es immer zwei benachbarte Elemente vergleicht und ein falsch geordnetes Paar tauscht. Bei aufsteigender Sortierung wandern so große Werte Runde für Runde nach rechts. Du lernst, die Schritte selbst auszuführen, die Abbruchoptimierung zu erklären und den Aufwand einzuschätzen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie funktioniert ein einzelner Durchgang?
Beginne links. Vergleiche ein Element mit seinem rechten Nachbarn. Ist der linke Wert größer, vertauschst du beide. Dann rückst du um eine Position nach rechts und vergleichst das nächste Nachbarpaar.
Sortiere [5, 1, 4, 9, 0] aufsteigend. In der ersten Runde passiert Folgendes:
5 > 1: tauschen →[1, 5, 4, 9, 0]5 > 4: tauschen →[1, 4, 5, 9, 0]5 < 9: nicht tauschen →[1, 4, 5, 9, 0]9 > 0: tauschen →[1, 4, 5, 0, 9]
Jetzt steht 9, der größte Wert, ganz rechts. Vier Nachbarvergleiche waren nötig, also bei fünf Elementen genau $n-1=4$ Vergleiche.
Nach einer vollständigen Runde steht das größte Element des bearbeiteten Bereichs an dessen rechtem Ende.
Wie wird die ganze Liste sortiert?
Nach der ersten Runde ist nur der letzte Platz sicher. Deshalb wiederholst du das Verfahren für den noch unsortierten Bereich. Die rechte Grenze rückt nach jeder Runde um eine Position nach links.
Beim Beispiel [5, 1, 4, 9, 0] lauten die Rundenergebnisse:
[1, 4, 5, 0, 9]—9steht richtig.[1, 4, 0, 5, 9]—5steht nun ebenfalls richtig.[1, 0, 4, 5, 9]—4steht richtig.[0, 1, 4, 5, 9]— die Liste ist vollständig sortiert.
Die feste Variante benötigt hier $4+3+2+1=10$ Nachbarvergleiche.
Deine Sortierübung
Sortiere [4, 2, 3, 1] mit Bubblesort. Notiere in jeder Runde die verglichenen Paare, ob du tauschst, und das Ergebnis der Runde.
Lösung:
- Runde:
4 > 2→ tauschen:[2, 4, 3, 1];4 > 3→ tauschen:[2, 3, 4, 1];4 > 1→ tauschen:[2, 3, 1, 4]. - Runde:
2 < 3→ nicht tauschen:[2, 3, 1, 4];3 > 1→ tauschen:[2, 1, 3, 4]. - Runde:
2 > 1→ tauschen:[1, 2, 3, 4].
Kontrolle: Rechts wächst der sortierte Bereich in jeder Runde um mindestens ein Element. Insgesamt wurden $3+2+1=6$ Nachbarpaare verglichen.
Wie sieht der Algorithmus aus?
Für eine aufsteigende Sortierung brauchst du eine äußere Wiederholung für die Runden und eine innere Wiederholung für die Nachbarvergleiche.
Tauschvariable
Eine Tauschvariable speichert einen Wert kurz zwischen. So geht beim Vertauschen zweier Listeneinträge keiner der beiden Werte verloren.
Eine optimierte Beschreibung lautet:
- Setze die rechte Grenze auf die Länge der Liste.
- Setze zu Beginn jeder Runde
getauschtauffalsch. - Vergleiche alle Nachbarpaare links von der Grenze.
- Falls
links > rechtsgilt, tausche beide Werte und setzegetauschtaufwahr. - Verschiebe die rechte Grenze um eine Position nach links.
- Beende den Algorithmus, wenn kein Tausch stattfand oder nur noch ein Element im unsortierten Bereich liegt. Andernfalls beginne die nächste Runde.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Bei aufsteigender Sortierung wird getauscht, wenn der linke Wert als der rechte ist. Nach einer Runde steht das Element des bearbeiteten Bereichs rechts. Eine Runde ohne Tausch zeigt, dass die Liste bereits ist.
Warum ist das Ergebnis korrekt?
Eine wichtige Beobachtung bleibt nach jeder abgeschlossenen Runde wahr: Rechts steht ein wachsender Bereich mit den größten bereits richtig platzierten Elementen.
Schleifeninvariante
Eine Schleifeninvariante ist eine Aussage, die vor oder nach jeder Wiederholung an einer festgelegten Stelle gilt. Sie hilft zu begründen, warum ein Algorithmus am Ende das gewünschte Ergebnis liefert.
Für Bubblesort lautet die Begründung:
- Nach der ersten Runde steht das Maximum der ganzen Liste rechts.
- In der nächsten Runde wird dieser Platz nicht mehr bearbeitet. Das Maximum des verbleibenden Bereichs wandert an dessen rechtes Ende.
- So wächst der korrekt sortierte rechte Bereich Runde für Runde.
- Wenn nur noch ein Element übrig ist, müssen alle Elemente geordnet sein. Die Liste enthält weiterhin dieselben Werte, weil Bubblesort nur vertauscht.
Bei der optimierten Variante gilt zusätzlich: Gab es in einer ganzen Runde keinen Tausch, war kein benachbartes Paar falsch geordnet. Daher ist die gesamte Liste aufsteigend sortiert.
Welche Eigenschaften hat Bubblesort?
Stabilität
Ein Sortierverfahren ist stabil, wenn gleichwertige Elemente ihre ursprüngliche Reihenfolge behalten. Klassischer Bubblesort ist stabil, sofern nur bei links > rechts und nicht bei Gleichheit getauscht wird.
Beispiel: In [2A, 1, 2B] markieren A und B die ursprüngliche Reihenfolge der beiden gleichen Werte. Nach dem Sortieren entsteht [1, 2A, 2B]; 2A bleibt vor 2B.
In-place
Ein Verfahren arbeitet in-place, wenn es die vorhandene Liste direkt verändert und keine zweite vollständige Liste zum Sortieren benötigt. Bubblesort braucht nur wenig zusätzlichen Speicher, etwa für die Tauschvariable und Steuerwerte.
Die Vorteile sind Anschaulichkeit und eine einfache Umsetzung. Der entscheidende Nachteil ist der hohe Aufwand bei großen Listen. Deshalb dient Bubblesort vor allem dazu, Sortierabläufe, Korrektheit und Laufzeit zu verstehen.
Wie groß ist der Aufwand?
Bei der festen Variante werden die Vergleichszahlen der Runden immer kleiner:
$$(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}$$
Die Zahl der Vergleiche wächst damit quadratisch. Verdoppelt sich $n$, vervierfacht sich der führende quadratische Anteil ungefähr. Worst Case und durchschnittlicher Fall liegen deshalb in $O(n^2)$; im Worst Case ist der Aufwand genauer $\Theta(n^2)$.
Für $n=5$ ergibt die feste Variante:
$$\frac{5\cdot(5-1)}{2}=10$$
Das stimmt mit den zehn Vergleichen im vollständigen Zahlenbeispiel überein.
Die Abbruchoptimierung ändert den Best Case
Eine bereits sortierte Liste benötigt bei der optimierten Variante nur eine Runde mit $n-1$ Vergleichen. Danach zeigt getauscht = falsch, dass der Algorithmus stoppen kann. Dieser Best Case hat linearen Aufwand $\Theta(n)$.
Ohne diese Prüfung führt die feste Variante ihre vorgesehenen Runden weiter aus. Ihr Best Case bleibt deshalb quadratisch. Die Aussage „Bubblesort hat im Best Case lineare Laufzeit“ gilt also nur für die vorzeitig abbrechende Variante.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Bubblesort
- Prinzip: benachbarte Werte vergleichen und nötigenfalls tauschen
- Fortschritt: sortierter rechter Bereich wächst nach jeder Runde
- Korrektheit: das Maximum des Restes erreicht seine endgültige Position
- Optimierung: nach einer tauschfreien Runde abbrechen
- Eigenschaften: stabil und in-place
- Aufwand: Best Case optimiert linear, Durchschnitt und schlechtester Fall quadratisch
Abschluss-Check
Du kannst Bubblesort sicher anwenden, wenn du bei jedem Schritt das Ziel der Ordnung prüfst, nach jeder Runde den wachsenden rechten Bereich markierst und feste sowie optimierte Variante auseinanderhältst.