ℹ️ Insertion Sort – Erklärung
Idee — Stell dir eine Hand Spielkarten vor: Du hältst links bereits sortierte Karten und nimmst eine neue Karte (den Schlüssel) aus dem rechten Bereich. Du verschiebst Karten nach rechts, bis die richtige Lücke gefunden ist, und legst den Schlüssel hinein. Der sortierte Bereich wächst um eine Karte.
Komplexität — O(n²) im Worst-Case (umgekehrt sortiertes Array), O(n) im Best-Case (bereits sortiert – nur Vergleiche, keine Verschiebungen). Besser als Bubble Sort in der Praxis für kleine Arrays.
Eigenschaften
  • Stabil: Ja – gleiche Werte behalten ihre Reihenfolge.
  • In-place: Ja – O(1) Zusatzspeicher.
1 / 30
ArrayKlick = Wert bearbeiten · Rechtsklick = löschen
64
0
34
1
25
2
12
3
22
4
11
5
90
6
+
_
Start: Index 0 ist trivial sortiert. Insertion Sort nimmt ab Index 1 jedes Element als Schlüssel und fügt es an die richtige Stelle im sortierten linken Bereich ein.
Schlüssel (schwebend)VerglichenSortiert (final)→verschoben (Kopie)