InsertionSort (Sortieren durch Einfügen) ist ein sehr einfaches vergleichsbasiertes Sortierverfahren. Es hat eine langsamere Laufzeit als die bekannteren Sortierverfahren wie MergeSort, QuickSort oder HeapSort. Dennoch bietet es einige Vorteile:
Idee
Die zu sortierende Folge a0, ... ,an-1 wird am Anfang und nach jedem Iterationsschritt in zwei Folgen aufgeteilt: Der erste Teil a0, ... ,ai-1 ist bereits (aufsteigend) sortiert, der zweite Teil ai, ... ,an-1 bleibt noch unsortiert.
Am Anfang bildet die leere Menge vorne den ersten Teil und die gesamte unsortierte Folge den zweiten Teil. Das Element ai wird nun als nächstes an die richtige Stelle in den bereits sortierten Teil eingefügt. Damit ist der sortierte Teil um ein Element größer geworden, sodass im nächsten Iterationsschritt dieses Verfahren wiederholt wird, bis zum Schluss alle Elemente im sortierten Teil sich befinden und die Folge sortiert ist.
Applet
© Miao Wang 2006 (Bug-Meldungen bitte an Webmaster@Wanginator.de richten)
Das Applet (benötigt Java) visualisiert einen InsertionSort auf maximal 16 Elemente. Dabei wird stets das erste Element aus der unsortierten Folge entnommen und als einzufügendes Element in die bereits sortierte Folge eingefügt. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.
Quellcode (Java)
Varianten
Im Jahre 1959 veröffentlichte D.L. Shell eine substanzielle Verbesserung dieses Algorithmus vor, indem statt benachbarter Elemente, Elemente, die durch eine bestimmte Distanz voneinander getrennt sind, verglichen werden. Dabei wird diese Distanz wird bei jedem Durchgang verringert. Dieser Algorithmus wurde nach dessen Autor ShellSort genannt.
Im Jahre 2004 veröffentlichten Bender, Farach-Colton und Mosteiro eine neue Variante des InsertionSort namens LibrarySort oder Gapped InsertionSort, welches einige ungenutzte Freiräume im Array hinterlässt ("gaps). Der Vorteil besteht darin, dass Elemente nur bis zu einem Freiraum verschoben werden mussten. Es kann gezeigt werden, dass dieser Algorithmus mit hoher Wahrscheinlichkeit in O(n log n) liegt. [3]
Analyse
Die Anzahl der Vergleiche des Verfahren ist abhängig von der Anordnung der Elemente in der unsortierten Folge. Zusätzlich sind Verschiebungen nötig, falls auf einem Array gearbeitet wird, wo die Elemente nach dem neu eingefügten Element verschoben werden. Die Verschiebungen sind vergleichsweise teuer, da das Finden der richtigen Stelle über eine binäre Suche beschleunigt werden kann. Da aber die größeren Elemente alle eins nach rechts rücken müssen, um die Einfügeposition frei zu machen, ist für das Einfügen ohnehin lineare Zeit erforderlich.
Im Best Case ist die Folge bereits sortiert, die Laufzeit beträgt dann O(n), da jedes einzufügende Element nur ein Vergleich mit dem Element links davon benötigt.
Im Average und Worst Case beträgt die Komplexität O(n2). Der Worst Case trifft ein, wenn das einzufügende Element stets an allererster Stelle eingefügt werden muss (z.B. bei einer invers sortierten Folge) und berechnet sich mit
.
Weiterführende Links und Literatur
