Insertionsort

Einführung

Der Algorithmus dieses Sortierverfahrens ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.

Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

Beispiel

Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.

5	7	0	3	4	2	6	1	(0)
5	7	0	3	4	2	6	1	(0)
0	5	7	3	4	2	6	1	(2)
0	3	5	7	4	2	6	1	(2)
0	3	4	5	7	2	6	1	(2)
0	2	3	4	5	7	6	1	(4)
0	2	3	4	5	6	7	1	(1)
0	1	2	3	4	5	6	7	(6)

Pseudocode

Der Algorithmus sieht im Pseudocode so aus:

prozedur insertionSort(A ist Liste sortierbarer Elemente)
    n = Länge von A
    für i von 1 bis n - 1 wiederhole
        einzusortierenderWert = A[i]
        j = i - 1
        solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
            A[j + 1] = A[j]
            j = j - 1
        ende solange
        A[j + 1] = einzusortierenderWert
    ende für
ende prozedur

Komplexität

Best Case

Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente [math]\displaystyle{ n }[/math].

Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von [math]\displaystyle{ O(n) }[/math].

Average Case

Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei [math]\displaystyle{ O(n^2) }[/math].

Worst Case

Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

[math]\displaystyle{ [11, 7, 5, 3, 2, 0] }[/math]

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen [math]\displaystyle{ c }[/math] gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt [math]\displaystyle{ n }[/math].

Beim ersten äußeren Schleifendurchlauf ist [math]\displaystyle{ c = 1 }[/math], da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit [math]\displaystyle{ n - 1 }[/math] Vergleichen.

Die Gesamtanzahl der Vergleiche ergibt sich zu:

[math]\displaystyle{ 1 + 2 + 3 + \dots + (n - 1) }[/math]

Dies ist eine arithmetische Reihe. Mit der gaußschen Summenformel erhält man:

[math]\displaystyle{ \frac{n(n-1)}{2} }[/math]

Für große [math]\displaystyle{ n }[/math] dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse [math]\displaystyle{ O(n^2) }[/math] liegt.