Einfügesortierung

Einfügesortierung (englisch: Insertion Sort) funktioniert ähnlich wie viele Menschen instinktiv Spielkarten auf der Hand sortieren: Du nimmst eine Karte und schiebst sie an die richtige Position zwischen die bereits sortierten Karten. So entsteht nach und nach eine vollständig sortierte Reihe.

So funktioniert Einfügesortierung

Stell dir die Liste [5, 2, 8, 3, 9] vor:

• Beginne mit dem zweiten Element. Das erste gilt als "bereits sortiert".
• Nimm 2: Ist es kleiner als 5? Ja → verschiebe 5 nach rechts, füge 2 ein → [2, 5, 8, 3, 9]
• Nimm 8: Ist es kleiner als 5? Nein → bleibt → [2, 5, 8, 3, 9]
• Nimm 3: Vergleiche rückwärts: kleiner als 8? Ja → verschiebe. Kleiner als 5? Ja → verschiebe. Kleiner als 2? Nein → füge ein → [2, 3, 5, 8, 9]
• Nimm 9: Größer als alle → bleibt → [2, 3, 5, 8, 9]

Python-Implementierung

def einfuege_sortierung(elemente):
    for i in range(1, len(elemente)):
        schluessel = elemente[i]    # aktuelles Element zum Einsetzen
        j = i - 1
        
        # Verschiebe größere Elemente nach rechts
        while j >= 0 and elemente[j] > schluessel:
            elemente[j + 1] = elemente[j]
            j -= 1
        
        # Schlüssel an der richtigen Stelle einfügen
        elemente[j + 1] = schluessel
    
    return elemente

zahlen = [5, 2, 8, 3, 9]
print(einfuege_sortierung(zahlen))   # [2, 3, 5, 8, 9]

Schritt-für-Schritt-Visualisierung

Für [5, 2, 8, 3, 9]:

Stärken von Einfügesortierung

Einfügesortierung hat gegenüber Bubble-Sort und Auswahlsortierung einen wichtigen Vorteil: Bei fast sortierten Listen ist sie sehr schnell:

# Fast sortierte Liste — Einfügesortierung ist hier sehr effizient
fast_sortiert = [1, 2, 4, 3, 5]   # nur ein Tausch nötig

Im besten Fall (bereits sortierte Liste) macht Einfügesortierung nur n - 1 Vergleiche — das ist O(n), viel besser als O(n²)!

Vergleich der drei einfachen Algorithmen