|
InsertionSort (engl. insertion - Einfügen) ist ein einfacher stabiler Sortieralgorithmus.
| Inhaltsverzeichnis |
|
1 Prinzip
2 Beispiel
3 Implementierung
4 Komplexität
5 Verwandter Sortieralgorithmus
6 Weblinks
|
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) sortierte Ausgabemenge ein. Dieser Vorgang
wiederholt sich solange, bis alle Elemente (ein)sortiert sind.
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 beginned,
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 beginned,
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 beginned,
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 beginned,
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 beginned,
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
Hier eine Implementierung in 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] > Menge[Einfuegeposition]) AND
(Einfuegeposition > Links)) DO
BEGIN
Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
Einfuegeposition := Einfuegeposition - 1;
END;
END;
Menge[Einfuegeposition] := Zwischenspeicher;
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.
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.
Verwandter Sortieralgorithmus
D.L. Shell schlug eine substantielle Verbeserung dieses Algorithmus vor, das heute unter dem Namen Shellsort bekannt wurde. Statt benachbarte Elemente werden Element, 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.inf.ethz.ch/~staerk/algorithms/SortAnimation.html)
|
