Python-Algorithmen

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.

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

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.

Vom Kartensortieren zum Code
current = result[index]🃏 Die nächste Karte aufnehmen
result[position] > current👈 Ist die Karte links größer?
result[position + 1] = result[position]➡️ Die größere Karte einen Platz nach rechts schieben
result[position + 1] = current📥 Die Karte in die Lücke legen
Der linke Teil ist immer sortiert; jedes neue Element wird darin eingefügt.
In einem Satz

Insertion 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

  1. for index in range(1, len(result)): beginnt beim zweiten Element; ein einzelnes Element ist schon sortiert.
  2. current hält den einzufügenden Wert fest, während größere Werte verschoben werden.
  3. while position >= 0 and result[position] > current: schiebt jeden größeren Wert einen Platz nach rechts.
  4. result[position + 1] = current legt 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.insort findet 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

Code ausführen →
main.py
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]))
Run-Button für dieses Beispiel erstellen

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.

  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

current innerhalb der Schleife zurückschreiben

Der Wert darf nur einmal gesetzt werden, nachdem alle größeren Werte verschoben sind.

Problem
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Lösung
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