Insertion-sort

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

Worst Case

Eine Liste in umgekehrter Reihenfolge stellt das Worst-Case-Szenario für InsertionSort dar:

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

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen c gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt n.

Beim ersten äußeren Schleifendurchlauf ist c = 1, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit n−1 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 n dominiert der quadratische Term, sodass InsertionSort im Worst Case in der Komplexitätsklasse [math]\displaystyle{ O(n^2) }[/math] liegt.

Best Case

Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt. Die Gesamtanzahl der Vergleiche ist somit proportional zu n.

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