Overview
Aufbau eines sortierten Präfixes durch wiederholtes Einfügen des nächsten Elements an die richtige Position.
Analogy
Spielkarten sortieren: jede neue Karte wird von rechts nach links an die richtige Stelle geschoben.
Step-by-step
- Starte mit Element an Index 1.
- Speichere den aktuellen Schlüssel (key = arr[i]).
- Verschiebe alle größeren Elemente links davon um eine Position nach rechts.
- Füge den Schlüssel in die entstandene Lücke ein.
- Wiederhole bis das Array vollständig sortiert ist.
Visual
[5,1,4,2,8]: Schritt 1→[1,5,4,2,8]; Schritt 2→[1,4,5,2,8]; Schritt 3→[1,2,4,5,8]
Common mistakes
- Inner-Loop-Grenze vergessen: Vergleich muss stoppen, wenn j<0 oder arr[j]<=key.
- Beim fast sortierten Array ist Insertion Sort mit O(n) optimal – diesen Vorteil nicht übersehen.
Practice questions
- Insertion Sort für eine Liste von Strings nach Länge implementieren.
- Zählen, wie viele Vertauschungen nötig sind (entspricht Anzahl von Inversionen).
Time
O(n²) worst-case, O(n) best-case (bereits sortiert)