Vorlesung Informatik 2 - Teil B: Theorie

2.4 Insertion-Sort

Sortieren durch Einfügen: dieses Verfahren ist eine Mischung aus Selection- und Bubble-Sort. 

Eine erste Erwähnung in der Literatur erfolgte 1946 durch John William Mauchly, des Erfinders des ENIAC Computers.

Wir gehen von links nach rechts durch den Array und fügen jeden weitere Element an sein richtige Stelle im Array links vom aktuelle Element ein.  

Beispiel:

13  4  25  17  2 43 8     wir beginnen mit der 4. Sie ist kleiner als 13 und muss nach links
 4 13  25  17  2 41 8     der grüne Teil des Arrays ist schon sortiert, die 25 steht auch schon richtig
 4 13  25  17  2 41 8     die 17 muss vor die 25
 4 13  17  25  2 41 8     jetzt müssen 45,17,13 und 2 nach rechts verschoben werden um für die 2 Platz zu machen
 2  4  13  17 25 41 8     die 41 ist schon größer als 25
 2  4  13  17 25 41 8     41,25,17 und 13 müssen um 1 nach rechts verschoben werden
 2  4   8  13 17 25 41    fertig

Der innere Teil des Algorithmus fügt das Element am Index k an seine richtige Position j, wobei der Bereich [0,k-1] schon sortiert ist. Um Platz zu schaffen, muss er  k-j Elemente um eine Position nach rechts verschieben. 

Eine binäre Suche im sortierten Bereich kann die Zahl der Vergleiche von O(N) auf O(log N) reduzieren, aber das Verschieben der Elemente hat trotzdem die Komplexität O(N).

Den inneren Teil müssen wir von i=1 bis N.-1 wiederholen, sodass die Gesamtkomplexität O(N2) ist.

Allerdings reduziert sich die Komplexität wie beim Bubble-Sort auf O(N), wenn die Daten schon sortiert sind.
Für den Fall, dass der Array so teilsortiert ist, dass kein Element weiter als d Stellen von seiner sortierten Position entfernt ist, ist die Komplexität O(d·N) so dass wir  für d<<N  die Komplexität O(N) erhalten.

Zusammenfassung: 
 in-situ, stabil
O(N2) maximal
O(N) für schon sortierte oder stark teilsortierte Daten

Der innere Teil lässt sich als Pseudocode so schreiben:

elementAnRichtigePosition(a, k) {    // Element a[k] an richtige Position innerhalt a[0,k] setzen
      key = a[k];
      while(k>0 && a[k-1]>key) {
            a[k] = a[k-1];
            k--;
       }
       a[k]=key;
}


Lehrvideo  (YouTube)