Kurs:Algorithmen und Datenstrukturen/Kapitel 2/InsertionSort

Herleitung

Insertion Sort hält, was der Name verspricht. Anstatt wie beim Selection Sort immer das kleinste Element herauszupicken und am ende einer sortierten Reihe zu hängen, nehmen wir ein Element nach dem anderen und fügen es in eine sortierte Reihe.

Am besten lässt sich der Algorithmus nicht ahand vom ersten, sondern von einem späteren Durchgang erklären. Wir nehmen an, wir hätten ein Array von $n$ Elementen von denen die ersten $1$ bis $(i-1)$ten Element sortiert sind. Im gegensatz zum Selection Sort sind aber die Elemente rechts vom $i$ten Element nicht alle größer als das $(i-1)$te Element.

Wir wollen nun das $i$te Element nach links schieben und zwar so, dass die $1$ bis $i$ten Elemente sortiert sind. Aus BubbleSort wissen wir, dass wir das $i$te Element so lange mit dem linken Nachbar vertauschen können, bis es an der richtigen Stelle sitzt.

In Oberon sieht das ganze dann in etwa so aus:

 1. PROCEDURE InsertionSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
 2.     VAR
 3.         i, k, temp : INTEGER;
 4.     BEGIN

            (* Ueberprüfe die Arraylänge *)
 5.         IF n > LEN(a) THEN
 6.             Out.String("Fehler: n ist größer als die Arraylaenge!"); Out.Ln;
 7.             RETURN;
 8.         END;

            (* Für jedes Element... *)
 9.         FOR i := 1 TO n-1 DO
10.             k := i-1;

                (* Verschiebe es bis zur richtigen Position *)
11.             WHILE (k >= 0) & (a[k] > a[k+1]) DO
12.                 temp := a[k]; a[k] := a[k+1]; a[k+1] := temp;
13.                 DEC(k);
14.             END;

15.         END;
16.     END InsertionSort;

Die Hauptschleife (Zeilen 9 bis 15) laeuft ab dem zweiten Element (Index 1) der Liste da das erste Element schon sortiert ist (eine Folge aus nur einem Element ist immer sortiert). Beim Verschieben des neuen Elementes muessen wir auch aufpassen (Zeile 11), dass wir nicht ueber den linken Rand des Arrays fallen (k >= 0).

Average-Case Analyse

In jedem Schritt des Algorithmus, verschieben wir ein Element von der Position $i$ zu ihrer richtigen Position, sagen wir $j$. Sind die Elemente zufaellig verteilt, so liegt $j$ irgendwo zwischen $1$ und $i$.

Die Wahrscheinlichkeit, dass das $i$te Elemente an der Position $j$ verschoben werden muss ist daher einfach ${\frac {1}{i}}$. Die Anzahl Vertauschungen, welche noetig sind, um das Element von $i$ nach $j$ zu verschieben ist $(i-j)$. Fuer alle moegliche $j$ ergibt das im Durchschnitt

$V(i)$	$=$	$\sum _{j=1}^{i}{\frac {1}{i}}(i-j)$
	$=$	${\frac {1}{i}}\left(\sum _{j=1}^{i}i-\sum _{j=1}^{i}j\right)$
	$=$	${\frac {1}{i}}\left(i^{2}-{\frac {i(i+1)}{2}}\right)$
	$=$	${\frac {i-1}{2}}$

Da wir immer zwei Elemente vergleichen bevor wir sie vertauschen oder eben nicht, ist die durchschnittliche Anzahl Vergleiche fuer ein Element an der Stelle $i$:

$V(i)+1$.

Fuer alle Elemente von $i=2$ (das erste Element ist ja schon sortiert) bis $i=n$ ist die durchschnittliche Anzahl Vertauschungen also

$\sum _{i=2}^{n}{\frac {i-1}{2}}\quad =\quad {\frac {n(n-1)}{4}}\quad \in \quad {\mathcal {O}}(n^{2})$

Analog dazu ist die durchschnittliche Anzahl Vergleiche

$\sum _{i=2}^{n}{\frac {i+1}{2}}\quad =\quad {\frac {n(n+2)}{4}}-1\quad \in \quad {\mathcal {O}}(n^{2})$

Die Anzahl Vergleiche ist somit kleiner als bei SelectionSort und BubbleSort, obwohl sie fuer alle drei Algorithmen in ${\mathcal {O}}(n^{2})$ liegt.

Erste Verbesserung: Binary Insertion Sort

Unser InsertionSort hat noch eine leicht vermeidbare Ineffizienz: wird das $i$te Element in die sortierte Folge eingefuegt, wird deren Position linear, Element fuer Element gesucht. Da wir aber wissen, dass unser Array von $a_{1}$ bis $a_{i-1}$ sortiert ist, koennen wir die Position des $i$ten Elementes mittels binaerer Suche ermitteln.

Das Nachruecken der Elemente um das $i$te Element einzufuegen laesst sich nicht vermeiden, wir brauchen aber dafuer nur $\log _{2}i$ Vergleiche anstatt ${\frac {i-1}{2}}$ wie bis anhin.

Die Implementation in Oberon sieht wie folgt aus:

 1. PROCEDURE BinInsertionSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
 2.     VAR
 3.         i, l, r, m, k, temp : INTEGER;
 4.     BEGIN

            (* Ueberprüfe die Arraylänge *)
 5.         IF n > LEN(a) THEN
 6.             Out.String("Fehler: n ist groesser als die Arraylaenge!"); Out.Ln;
 7.             RETURN;
 8.         END;

            (* Für jedes Element... *)
 9.         FOR i := 1 TO n-1 DO

                (* Suche deren Position zwischen l und r *)
10.             l := -1; r := i;
11.             WHILE r-l > 1 DO
12.                 m := (l+r) DIV 2;
13.                 IF a[m] < a[i] THEN
14.                     l := m;
15.                 ELSE
16.                     r := m;
17.                 END
18.             END;

                (* Verschiebe das Element zu dieser Position *)
19.             FOR k := i-1 TO r BY -1 DO
20.                 temp := a[k]; a[k] := a[k+1]; a[k+1] := temp;
21.             END

22.         END;

23.     END BinInsertionSort;

Die Hauptschleife (Zeilen 9 bis 22) laeuft, wie beim normalen InsertionSort, ab dem zweiten Element ueber alle Elemente. In den Zeilen 10 bis 18 wird die Position des iten Elementes gesucht. Am Ende dieser Schleife wissen wir, dass das ite Element zwischen dem lten und dem rten Element liegen muss, also muessen wir das ite Element mit dem linken Element vertauschen, bis es an der rten Stelle liegt (Zeilen 19 bis 21).

An der Anzahl Vertauschungen hat sich gegenüber dem alten InsertionSort nichts verändert. Jedes Element wird nach wie vor an der gleichen Position geschoben. Nur die Suche nach dieser Position -- und die damit verbundene Anzahl Vergleiche, ist anders.

Anstatt bei der Suche nach der Position des $i$ten Elementes ${\frac {i-1}{2}}$ Vergleiche zu verwenden, brauchen wir nur noch deren $\lceil \log _{2}i\rceil$. Beim Suchen der richtigen Position für $2\dots (n-1)$ Elementen benötigen wir im Schnitt

$\sum _{i=2}^{n}\log _{2}i\quad =\quad \log _{2}\left(\Gamma (n+1)\right)\quad \in \quad {\mathcal {O}}(n\log n)$

Vergleiche.