Eine Liste von Elementen zu sortieren ist eine der häufigsten Aufgaben in der Informatik. Es gibt viele verschiedene Algorithmen dafür, jeder mit unterschiedlichen Vor- und Nachteilen. Bubble-Sort ist einer der einfachsten zu verstehen und ein perfekter Einstieg. Er funktioniert, indem benachbarte Elemente wiederholt verglichen und bei falscher Reihenfolge getauscht werden.
So funktioniert Bubble-Sort
Stell dir vor, du hast die Liste [5, 3, 8, 1, 4] und möchtest sie aufsteigend sortieren.
In jedem Durchlauf gehst du von links nach rechts durch die Liste und vergleichst je zwei benachbarte Elemente:
- Ist das linke Element größer als das rechte, tausche sie.
- Ansonsten weiterziehen.
Nach einem vollständigen Durchlauf ist das größte Element ans Ende "geblasen". Nach jedem weiteren Durchlauf ist das nächste größte Element an der richtigen Position.
Durchlauf 1 durch [5, 3, 8, 1, 4]:
| Schritt | Vergleich | Aktion | Liste |
|---|---|---|---|
| 1 | 5 vs 3 | Tausch | [3, 5, 8, 1, 4] |
| 2 | 5 vs 8 | Kein Tausch | [3, 5, 8, 1, 4] |
| 3 | 8 vs 1 | Tausch | [3, 5, 1, 8, 4] |
| 4 | 8 vs 4 | Tausch | [3, 5, 1, 4, 8] |
Nach Durchlauf 1 steht 8 am Ende — an der richtigen Position.
Python-Implementierung
def bubble_sort(elemente):
n = len(elemente)
for durchlauf in range(n - 1):
for i in range(n - 1 - durchlauf):
if elemente[i] > elemente[i + 1]:
# Benachbarte Elemente tauschen
elemente[i], elemente[i + 1] = elemente[i + 1], elemente[i]
return elemente
zahlen = [5, 3, 8, 1, 4]
print(bubble_sort(zahlen)) # [1, 3, 4, 5, 8]
Der Python-Tausch a, b = b, a ist eine elegante Möglichkeit, zwei Variablen in einer Zeile zu tauschen, ohne eine Hilfsvariable zu benötigen. In den meisten anderen Sprachen bräuchte man: temp = a; a = b; b = temp.
Anzahl der Vergleiche
Für eine Liste mit n Elementen macht Bubble-Sort im schlechtesten Fall ungefähr n²/2 Vergleiche:
- 10 Elemente → ca. 50 Vergleiche
- 100 Elemente → ca. 5.000 Vergleiche
- 1.000 Elemente → ca. 500.000 Vergleiche
Die Arbeit wächst sehr schnell — deshalb wird Bubble-Sort in der Praxis nicht für große Datenmengen verwendet.
Du kannst eine Verbesserung einbauen: Verfolge, ob im aktuellen Durchlauf ein Tausch stattgefunden hat. Wenn kein Tausch mehr nötig war, ist die Liste bereits sortiert und du kannst früher aufhören.
Optimierte Version
def bubble_sort_optimiert(elemente):
n = len(elemente)
for durchlauf in range(n - 1):
getauscht = False
for i in range(n - 1 - durchlauf):
if elemente[i] > elemente[i + 1]:
elemente[i], elemente[i + 1] = elemente[i + 1], elemente[i]
getauscht = True
if not getauscht:
break # Liste ist sortiert, keine weiteren Durchläufe nötig
return elemente
Bubble-Sort hat eine Zeitkomplexität von O(n²), was bedeutet, dass er bei großen Listen sehr langsam wird. In echten Programmen verwendet man Pythons eingebaute sorted()-Funktion, die einen viel schnelleren Algorithmus nutzt. Bubble-Sort wird vor allem studiert, um das Konzept von Sortieralgorithmen zu verstehen.
Übungsaufgaben
Wie sieht die Liste [9, 4, 6, 2, 7] nach einem vollständigen Durchlauf von Bubble-Sort aus?
Antwort anzeigen
Wie viele Durchläufe benötigt Bubble-Sort im schlechtesten Fall für eine Liste mit 5 Elementen? Erkläre warum.