Einfügesort

Einfügesort, auch Insertionsort genannt, ist ein einfaches Vergleichssortierverfahren. Es sortiert eine Folge, indem es sie schrittweise durchgeht und jedes neue Element an der richtigen Position in der bereits sortierten linken Teilliste einfügt.

Der Algorithmus beginnt mit dem ersten Element als sortiertem Teil. Anschließend wählt er das nächste Element, verschiebt alle größeren Elemente des sortierten Teils um eine Position nach rechts und platziert das aktuelle Element an der passenden Stelle.

Algorithmenbeschreibung: Für i von 1 bis n-1: key = a[i]; j = i-1; während j >= 0 und a[j] > key: a[j+1] = a[j]; j--; dann a[j+1] = key.

Eigenschaften: In-place, benötigt nur konstanten zusätzlichen Speicher. Stabil, da gleiche Schlüssel ihre relative Reihenfolge behalten. Zeitkomplexität: Durchschnitt und Worst Case O(n^2); Best Case O(n) bei bereits sortierter Eingabe. Die Anzahl der Verschiebungen hängt von der Distanz des Elements zur richtigen Position ab, was bei nahezu sortierten Listen gering ist.

Anwendungen: Geeignet für kleine Datensätze oder Listen, die fast sortiert sind; dient als Lehrbeispiel oder als Bestandteil hybrider Sortieralgorithmen (z. B. Timsort) für kleine Runs.

Varianten: Der binäre Insertionsort verwendet eine binäre Suche, um die Einfügeposition zu bestimmen, verschiebt aber weiterhin die Elemente.