Die Bestenliste muss stimmen
Ein Sortieralgorithmus bringt Daten in eine Reihenfolge, etwa Punkte vom höchsten zum niedrigsten. Du lernst drei: Bubble Sort, Insertion Sort und Merge Sort, und du siehst, wie sie sich in der Zahl der Schritte unterscheiden.
Jedes Spiel mit einer Bestenliste sortiert. Und eine sortierte Liste macht die binäre Suche aus der letzten Lektion erst möglich.
Am Ende dieser Lektion
Notiz
Ich kann eine Liste mit Bubble Sort, Insertion Sort und Merge Sort sortieren.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Sortieren | Daten in eine Reihenfolge bringen |
| Vergleich | der Test, welches von zwei Elementen größer ist |
| Tausch | zwei Elemente tauschen ihre Plätze |
| Durchlauf | einmal die ganze Liste entlanggehen |
| Verschmelzen | zwei sortierte Listen zu einer sortierten Liste zusammenfügen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Bubble Sort tauscht Nachbarn der Reihe nach
Bubble Sort vergleicht in jedem Durchlauf je zwei Nachbarn. Steht der linke Wert über dem rechten, tauschen beide den Platz. So wandert der größte Wert wie eine Blase ans Ende.
Nach dem ersten Durchlauf liegt der größte Wert richtig. Nach dem zweiten auch der zweitgrößte, und so weiter.
Beispiel: Bubble Sort auf 5, 2, 4, 1
| Durchlauf | Liste danach | Was passiert |
|---|---|---|
| Start | 5, 2, 4, 1 | Nichts getan |
| 1 | 2, 4, 1, 5 | Die 5 wandert ganz nach rechts |
| 2 | 2, 1, 4, 5 | Die 4 ist an ihrem Platz |
| 3 | 1, 2, 4, 5 | Fertig |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Insertion Sort steckt Werte an die richtige Stelle
Insertion Sort arbeitet wie jemand, der Spielkarten in der Hand sortiert. Links liegt ein schon sortierter Teil. Der nächste Wert wird herausgenommen und so weit nach links geschoben, bis er passt.
Der sortierte Teil wächst bei jedem Schritt um einen Wert.
Beispiel: Insertion Sort auf 5, 2, 4, 1
| Schritt | Sortierter Teil | Rest | Was passiert |
|---|---|---|
| Start | 5 | 2, 4, 1 | Ein Wert allein ist sortiert |
| 1 | 2, 5 | 4, 1 | Die 2 rutscht vor die 5 |
| 2 | 2, 4, 5 | 1 | Die 4 passt zwischen 2 und 5 |
| 3 | 1, 2, 4, 5 | | Die 1 rutscht ganz nach vorn |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele glauben, ein Durchlauf von Bubble Sort sortiere schon die ganze Liste. Er legt aber nur einen Wert an seinen Platz. Bei einer Liste mit n Werten brauchst du bis zu n minus 1 Durchläufe.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Die Schaltflächen Ausführen tippen ihren Befehl in das Terminal neben dem Lab. Jeder startet Python im Container jupyter.
Bubble Sort im Lab und seine Vergleiche
Der erste Befehl schreibt Bubble Sort in die Datei sortieren.py. Er gibt nichts aus. Der Code sortiert zehn Werte und zählt dabei jeden Vergleich. Der zweite Befehl startet die Datei.
Bubble Sort in sortieren.py schreiben
docker exec jupyter sh -c "printf 'werte = [5, 2, 4, 1, 3, 9, 7, 8, 6, 0]\nvergleiche = 0\nfor runde in range(len(werte) - 1):\n for i in range(len(werte) - 1 - runde):\n vergleiche = vergleiche + 1\n if werte[i] > werte[i + 1]:\n hilfe = werte[i]\n werte[i] = werte[i + 1]\n werte[i + 1] = hilfe\nprint(werte)\nprint(\"Vergleiche:\", vergleiche)\n' > sortieren.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Bubble Sort starten
docker exec jupyter python3 sortieren.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zum Vergleich: Pythons eigenes sorted
docker exec jupyter python3 -c "print(sorted([5, 2, 4, 1, 3, 9, 7, 8, 6, 0]))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Merge Sort verschmilzt kleine sortierte Listen
Merge Sort hat zwei Ideen. Erstens: Eine Liste mit einem Element ist schon sortiert. Zweitens: Zwei sortierte Listen lassen sich leicht zu einer sortierten Liste verschmelzen.
Also startest du mit lauter Listen aus einem Element und verschmilzt immer zwei Nachbarn, bis eine einzige Liste übrig ist.
Beispiel: [2, 5] und [1, 4] verschmelzen
| Vergleich | Kleineres | Ergebnis bisher |
|---|---|---|
| 2 gegen 1 | 1 | 1 |
| 2 gegen 4 | 2 | 1, 2 |
| 5 gegen 4 | 4 | 1, 2, 4 |
| Rest übrig: 5 | 5 | 1, 2, 4, 5 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Zwei sortierte Listen verschmelzen
a = [2, 5, 9]
b = [1, 4, 6, 8] # Ändere die Zahlen, aber lass beide Listen sortiert.
ergebnis = []
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
ergebnis.append(a[i])
i = i + 1
else:
ergebnis.append(b[j])
j = j + 1
ergebnis = ergebnis + a[i:] + b[j:] # Einer der beiden Reste ist leer.
print(ergebnis)
Das Verschmelzen in mischen.py schreiben
docker exec jupyter sh -c "printf 'a = [2, 5]\nb = [1, 4]\nergebnis = []\ni = 0\nj = 0\nwhile i < len(a) and j < len(b):\n if a[i] <= b[j]:\n ergebnis.append(a[i])\n i = i + 1\n else:\n ergebnis.append(b[j])\n j = j + 1\nergebnis = ergebnis + a[i:] + b[j:]\nprint(ergebnis)\n' > mischen.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Das Verschmelzen starten
docker exec jupyter python3 mischen.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend: die Vergleiche zählen
Bubble Sort hat bei zehn Werten 45 Vergleiche gebraucht. Wie viele wären es bei 20 Werten? Rate zuerst, ob es doppelt so viele werden. Die nächste Lektion zeigt dir die Antwort.