Kurs:Algorithmen und Datenstrukturen/Kapitel 2/InsertionSort

Aus Wikiversity

Insertion Sort[Bearbeiten]

Herleitung[Bearbeiten]

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 Elementen von denen die ersten bis ten Element sortiert sind. Im gegensatz zum Selection Sort sind aber die Elemente rechts vom ten Element nicht alle größer als das te Element.

Wir wollen nun das te Element nach links schieben und zwar so, dass die bis ten Elemente sortiert sind. Aus BubbleSort wissen wir, dass wir das 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[Bearbeiten]

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

Die Wahrscheinlichkeit, dass das te Elemente an der Position verschoben werden muss ist daher einfach . Die Anzahl Vertauschungen, welche noetig sind, um das Element von nach zu verschieben ist . Fuer alle moegliche ergibt das im Durchschnitt

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

.

Fuer alle Elemente von (das erste Element ist ja schon sortiert) bis ist die durchschnittliche Anzahl Vertauschungen also

Analog dazu ist die durchschnittliche Anzahl Vergleiche

Die Anzahl Vergleiche ist somit kleiner als bei SelectionSort und BubbleSort, obwohl sie fuer alle drei Algorithmen in liegt.

Erste Verbesserung: Binary Insertion Sort[Bearbeiten]

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

Das Nachruecken der Elemente um das te Element einzufuegen laesst sich nicht vermeiden, wir brauchen aber dafuer nur Vergleiche anstatt 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 ten Elementes Vergleiche zu verwenden, brauchen wir nur noch deren . Beim Suchen der richtigen Position für Elementen benötigen wir im Schnitt

Vergleiche.

Zweite Verbesserung: ShellSort[Bearbeiten]