Bubblesort (bubble sort) in Python
In dieser Lektion implementierst du Bubblesort und brichst vorzeitig ab, sobald die Liste sortiert ist.
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.
result[index] > result[index + 1]👫 Steht das größere Kind vorne?result[index], result[index + 1] = ...🔄 Die beiden Nachbarn tauschenfor end in range(len(result) - 1, 0, -1):🚶 Die Reihe noch einmal ablaufen, jedes Mal ein Kind kürzerif not swapped: break✅ Ein ganzer Durchgang ohne Tausch: die Reihe ist sortiertBubble 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
result = values.copy()sortiert eine Kopie, damit die Liste des Aufrufers unverändert bleibt.if result[index] > result[index + 1]:tauscht ein Paar, das falsch herum steht.endwird nach jedem Durchgang kleiner, weil die größten Werte schon am Ende stehen.if not swapped: breakbricht 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()undlist.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
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]))
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.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Einen Index zu weit gehen
result[index + 1] läuft über das Ende hinaus, wenn index die letzte Position erreicht.
for index in range(len(result)):
if result[index] > result[index + 1]:
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.
- Count Inversions Count the out-of-order pairs in a list. Schwierig
- Median einer Liste Finde den mittleren Wert einer Liste nach dem Sortieren. Einfach