InsertionSort (engl. insertion - Einfügen) ist ein einfacher stabiler Sortieralgorithmus.

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)