Insertionsort
InsertionSort (engl. insertion - Einfügen) ist ein einfaches stabiles Sortierverfahren. Er ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat er jedoch folgende Vorteile:
- einfach zu implementieren
- effizient bei (ziemlich) kleinen Eingabemengen
- effizient bei Eingabemengen, die schon weitgehend sortiert sind
- stabil (d.h., die Reihenfolge von schon sortierten Elementen ändert sich nicht)
- minimaler Speicherverbrauch
| Inhaltsverzeichnis |
Prinzip
Der Algorithmus entnimmt der unsortierten Eingabemenge ein beliebiges (z.B. das erste) Element und fügt es an richtiger Stelle in die (anfangs leere) Ausgabemenge ein. Das Verfahren arbeitet also in-place. Geht man in der Reihenfolge der ursprünglichen Menge vor, so ist es jedoch (etwa im Gegensatz zu Selectionsort) stabil. Wird auf einem Array gearbeitet, so müssen die Elemente nach dem neu eingefügten Element verschoben werden. Dies ist die eigentlich teure Operation von Insertionsort, da das Finden der richtigen Einfügeposition über eine binäre Suche vergleichsweise effizient erfolgen kann.
Pseudocode
Der folgende Pseudocode sortiert die Eingabemenge aufsteigend. Um eine absteigende Sortierung zu erreichen, ist der zweite Vergleich in Zeile 4 entsprechend zu ändern.
a: Liste (Array) mit der unsortierten Eingabemenge insertion_sort(a) 1 von j2 bis länge[a] 2 führe aus aktueller_wert
Beispiel
Hier ein Beispiel anhand einer zu sortierenden Menge aus 5 Integer-Werten:
unsortierte Eingabemenge: [ 3 2 5 1 4 ]
-------------------------------------------------------------------------------
[| 3 2 5 1 4 ] Das erste Element wird der Eingabemenge entnommen und
^ zwischengespeichert.
[ _ | 2 5 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[ 3 | 2 5 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[ 3 | 2 5 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[ _ 3 | 5 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[ 2 3 | 5 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[ 2 3 | 5 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[ 2 3 _ | 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[ 2 3 5 | 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[ 2 3 5 | 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[ _ 2 3 5 | 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[ 1 2 3 5 | 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[ 1 2 3 5 | 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[ 1 2 3 _ 5 |] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[ 1 2 3 4 5 |] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
sortierte Ausgabemenge: [ 1 2 3 4 5 ]
Implementierung
Im Folgenden wird InsertionSort in unterschiedlichen Programmiersprachen implementiert.
Pascal
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
VAR
Index, Einfuegeposition, Zwischenspeicher: INTEGER;
BEGIN
FOR Index := Links + 1 TO Rechts DO
BEGIN
Zwischenspeicher := Menge[Index];
Einfuegeposition := Index;
WHILE ((Menge[Einfugeposition - 1] > Zwischenspeicher) AND
(Einfuegeposition > Links)) DO
BEGIN
Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
Einfuegeposition := Einfuegeposition - 1;
END;
Menge[Einfuegeposition] := Zwischenspeicher;
END;
END;
Hinweise:
Mit MengeIntegerTyp ist ein beliebig großes Array für Integer-Werte gemeint, Links und Rechts sind die Grenzen dieses Arrays. Eine effizientere Implementierung ist möglich, wenn anstatt der Bedingung Einfuegeposition > Links in der While-Schleife ein sog. Stopelement verwendet wird.
Java
Diese Implementierung benutzt eine binäre Suche zur Bestimmung der richtigen Position des Elementes. Das heißt, wenn wir die richtige Position für das Element an Position i finden wollen, starten wir eine binäre Suche auf dem, schon sortierten Teilarray 0-(i-1) und verschieben alle Elemente, die größer als a[i] sind an a[i] nach rechts vorbei.
public static void inssort(int[] a) {
int pos;
for (int i = 1; i <= a.length - 1; i++) {
pos = binsearch(a, 0, i - 1, a[i]);
move(i, pos, a);
}
}
private static void move(int i, int j, int[] a) {
int tmp = a[i];
for (int g = i; g >= j + 1; g--) {
a[g] = a[g - 1];
}
a[j] = tmp;
}
private static int binsearch(int[] a, int low, int high, int x) {
int mitte = 0;
while (low <= high) {
mitte = (low + high) / 2;
if (a[mitte] == x)
return mitte;
if (a[mitte] < x)
low = mitte + 1;
if (a[mitte] > x)
high = mitte - 1;
}
return low;
}
Komplexität
Die Anzahl der Vergleiche und Verschiebungen des Algorithmus ist von der Anordnung der Elemente in der unsortierten Eingangsmenge abhängig. Für den Average-Case ist eine Abschätzung der Laufzeit daher nicht so einfach möglich. Im Best Case ist die Komplexität jedoch linear, im Worst Case dagegen quadratisch.
Wenn zur Bestimmung der richtigen Position eines Elementes die binäre Suche benutzt wird, kann man die Anzahl der Vergleiche, im Worst Case, durch log(n!) = nlogn − nloge + O(logn) = nlogn − 0,4426n + O(logn) abschätzen. Die Anzahl der Schiebeoperationen sind im Average-Case (n * (n − 1)) / 4 = O(n2).
Der Worst Case wäre ein absteigend sortiertes Array a, da wir bei jedem Element i die Methode move(i,0,a) aufrufen müssen. Die Anzahl der Schiebeoperationen beträgt in diesem Fall ((n * (n + 1)) / 2) − n = O(n2).
Verwandter Sortieralgorithmus
D.L. Shell schlug eine substanzielle Verbesserung dieses Algorithmus vor, die heute unter dem Namen Shellsort bekannt ist. Statt benachbarter Elemente werden Elemente, die durch eine bestimmte Distanz voneinander getrennt sind, verglichen. Diese Distanz wird bei jedem Durchgang verringert.
Weblinks
- http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html Java Beispiele
- http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insertion.htm
- http://wikisource.org/wiki/Insertion_sort
Siehe auch: Liste von Algorithmen