Insertionsort (insertion sort) in Python
In dieser Lektion implementierst du Insertionsort, indem du jedes Element an der richtigen Stelle im bereits sortierten Teil einfügst.
Einführung
Das Problem
Daten kommen oft fast sortiert an, oder ein Element nach dem anderen: Eine sortierte Punkteliste bekommt einen neuen Wert. Alles neu zu sortieren ist Verschwendung. Insertion Sort kommt mit diesem Fall sehr gut zurecht, und so sortieren viele Menschen Spielkarten von Hand.
Stell es dir so vor
Insertion Sort ist, wie du Karten auf der Hand sortierst. Du nimmst eine Karte nach der anderen auf und schiebst sie nach links an jeder größeren Karte vorbei, bis sie an der richtigen Stelle sitzt. Die Karten links davon sind immer geordnet.
current = result[index]🃏 Die nächste Karte aufnehmenresult[position] > current👈 Ist die Karte links größer?result[position + 1] = result[position]➡️ Die größere Karte einen Platz nach rechts schiebenresult[position + 1] = current📥 Die Karte in die Lücke legenInsertion Sort baut einen sortierten Teil Element für Element auf: Größere Elemente werden nach rechts verschoben, und das aktuelle Element kommt in die Lücke. Im schlechtesten Fall ist das O(n²), bei fast sortierten Daten aber nahe O(n).
Das Wichtigste
for index in range(1, len(result)):beginnt beim zweiten Element; ein einzelnes Element ist schon sortiert.currenthält den einzufügenden Wert fest, während größere Werte verschoben werden.while position >= 0 and result[position] > current:schiebt jeden größeren Wert einen Platz nach rechts.result[position + 1] = currentlegt den Wert in die entstandene Lücke.
Wann verwendet man das?
- Kleine oder fast sortierte Listen.
- Eine Liste sortiert halten, während neue Elemente ankommen.
- Als letzter Schritt in schnelleren Sortierverfahren, die für kleine Stücke auf Insertion Sort umschalten.
Wann du es nicht brauchst
- Große zufällige Listen: Das Verschieben wird langsam, nimm
sorted(). - Häufiges Einfügen in eine große sortierte Liste:
bisect.insortfindet die Position per binärer Suche.
Insertionsort (insertion sort) in Python visualisieren
O(n²)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
def insertion_sort(values):
result = values.copy()
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([9, 5, 1, 4, 3]))
Ergebnis der Ausführung
[1, 3, 4, 5, 9]
Erklärung des Codes
Die Variable current enthält den Wert, der eingefügt werden soll. Die while-Schleife schiebt alle Werte, die größer als current sind, um eine Position nach rechts und schafft so Platz, dann wird current dort eingesetzt. Im schlechtesten Fall ist die Komplexität O(n²), bei fast sortierten Daten kommt der Algorithmus aber nah an O(n) heran.
Ä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
current innerhalb der Schleife zurückschreiben
Der Wert darf nur einmal gesetzt werden, nachdem alle größeren Werte verschoben sind.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
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