Python-Algorithmen

Bubblesort (bubble sort) in Python

In dieser Lektion implementierst du Bubblesort und brichst vorzeitig ab, sobald die Liste sortiert ist.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Sortieren begegnet dir überall, und wenn du verstehst, wie es funktioniert, kannst du die Geschwindigkeit von Programmen besser einschätzen. Bubble Sort ist der Sortieralgorithmus, den man Schritt für Schritt am leichtesten nachvollziehen kann. Deshalb ist er meist das erste Beispiel, auch wenn echte Programme schnellere verwenden.

Stell es dir so vor

Bubble Sort ist, als würdest du Kinder nach Größe aufstellen und dabei immer nur zwei Nachbarn tauschen. Du gehst die Reihe entlang und tauschst jedes Paar, bei dem das größere Kind vorne steht. Nach einem Durchgang ist das größte Kind am Ende angekommen, wie eine Blase, die an die Oberfläche steigt. Das wiederholst du, bis du in einem Durchgang nichts mehr tauschen musst.

Von der Kinderreihe zum Code
result[index] > result[index + 1]👫 Steht das größere Kind vorne?
result[index], result[index + 1] = ...🔄 Die beiden Nachbarn tauschen
for end in range(len(result) - 1, 0, -1):🚶 Die Reihe noch einmal ablaufen, jedes Mal ein Kind kürzer
if not swapped: break✅ Ein ganzer Durchgang ohne Tausch: die Reihe ist sortiert
Nach jedem Durchgang steht der größte verbleibende Wert an seinem endgültigen Platz.
In einem Satz

Bubble Sort läuft wiederholt durch die Liste und tauscht benachbarte Elemente, die in der falschen Reihenfolge stehen, bis in einem ganzen Durchgang nichts mehr getauscht wird. Im Allgemeinen braucht er O(n²) Zeit.

Das Wichtigste

  1. result = values.copy() sortiert eine Kopie, damit die Liste des Aufrufers unverändert bleibt.
  2. if result[index] > result[index + 1]: tauscht ein Paar, das falsch herum steht.
  3. end wird nach jedem Durchgang kleiner, weil die größten Werte schon am Ende stehen.
  4. if not swapped: break bricht vorzeitig ab, wenn in einem Durchgang nichts getauscht wurde. Sortierte Eingaben sind so nach einem Durchgang fertig.

Wann verwendet man das?

  • Lernen, wie vergleichsbasiertes Sortieren funktioniert.
  • Winzige Listen in Lernwerkzeugen und Visualisierungen.
  • In einem Durchgang prüfen, ob eine Liste schon sortiert ist.

Wann du es nicht brauchst

  • Echte Programme: sorted() und list.sort() sind viel schneller (O(n log n)) und gut getestet.
  • Listen mit mehr als ein paar hundert Elementen: Die Zahl der Vergleiche wächst mit dem Quadrat der Länge.

Bubblesort (bubble sort) in Python visualisieren

O(n²)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Beispielcode

Code ausführen →
main.py
def bubble_sort(values):
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True
        if not swapped:
            break
    return result

print(bubble_sort([5, 1, 4, 2, 8]))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

[1, 2, 4, 5, 8]

Erklärung des Codes

Nach jedem Durchlauf steht der größte Wert des unsortierten Teils schon an seiner endgültigen Position, deshalb wird der nächste Durchlauf um ein Element kürzer. Die Variable swapped merkt sich, ob es in diesem Durchlauf eine Vertauschung gab. Gab es keine, ist die Liste schon sortiert und die Schleife endet vorzeitig. Im schlechtesten Fall ist die Komplexität O(n²), deshalb taugt der Algorithmus nicht für große Datenmengen.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Einen Index zu weit gehen

result[index + 1] läuft über das Ende hinaus, wenn index die letzte Position erreicht.

Problem
for index in range(len(result)):
    if result[index] > result[index + 1]:
Lösung
for index in range(end):
    if result[index] > result[index + 1]:

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges