Insertion Sort
Baut links eine sortierte Teilfolge auf und fügt jedes neue Element an die richtige Stelle ein.
- Vergleiche 0
- Verschiebungen 0
- Einsetzungen 0
- sortierte Indizes 1
- aktiv
- Vergleich
- Tausch
- sortiert
Pseudocode
1 for i from 1 to n - 1
2 key = a[i]
3 j = i - 1
4 while j >= 0 and a[j] > key
5 a[j + 1] = a[j]
6 j = j - 1
7 a[j + 1] = key
Schritt-Log
- 1Start.
Funktionsweise, Laufzeit und Speicher
Insertion Sort behandelt das Array wie einen Stapel Karten: links liegt der bereits sortierte Teil, rechts der unsortierte. In jedem Schritt nimmt der Algorithmus das erste unsortierte Element (den Key) und vergleicht es von rechts nach links mit allen Werten im sortierten Teil. Solange ein Wert größer als der Key ist, wird er um eine Position nach rechts geschoben. Sobald ein kleinerer Wert (oder der Anfang) erreicht ist, wird der Key in die entstandene Lücke gesetzt. Der sortierte Präfix wächst dadurch in jeder Iteration um eins. Im Best Case ist die Eingabe bereits sortiert und der innere Vergleich endet sofort, weshalb die Best-Case-Laufzeit linear ist (O(n)). Im Mittel und im Worst Case müssen pro Element bis zu i Werte verglichen und verschoben werden, was zu quadratischer Gesamtlaufzeit führt (O(n^2)). Insertion Sort arbeitet in-place und braucht nur konstant viel Zusatzspeicher (O(1)). Die Reihenfolge gleichwertiger Elemente bleibt erhalten, der Algorithmus ist also stabil.
Komplexität
- Best Case
- O(n)
- Average Case
- O(n2)
- Worst Case
- O(n2)
- Zusatz-Speicher
- O(1)
Wann verwenden?
Sehr stark bei kleinen Arrays mit weniger als rund 20 Elementen und bei nahezu sortierten Daten, wo die Laufzeit auf linear absinkt. Genau deshalb wechseln viele Hybrid-Sortierer wie Timsort intern auf Insertion Sort, sobald die rekursiven Teilbereiche klein genug sind.