Insertion Sort

Einführung

Der Algorithmus dieses Sortierverfahrens ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

Beispiel

Die folgende Tabelle zeigt die Sortier­schritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).

Man kann sich den Ablauf des Insertion Sort folgendermaßen vorstellen (http://en.wikipedia.org/wiki/Insertion_sort):

Pseudo Code

Der Algorithmus sieht im Pseudocode so aus:

prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)

wiederhole bis zur Länge von A und beginne beim 2. Element

einzusortierender_wert = A an der Stelle i

j = i

wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert

A an der Stelle j = A an der Stelle j-1

j = j − 1

ende wiederhole

A an der Stelle j = einzusortierender_wert

ende wiederhole

ende prozedur

Komplexität

Worst Case

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))

Hierbei handelt es sich um eine arithmetische Reihe, mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

c⋅(n−1+1)*((n−1)/2)=cn​2​​/2 − cn/2

Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse O(n​2​​)

Best Case

Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.