Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

37.1.3 Insertionsort

37.1.3 Insertionsort

Bisher waren die Algorithmen immer so konzipiert, dass in jedem Schritten, immer die komplette Liste durchlaufen werden musste und oftmals dann sogar nichts mehr gemacht wurde (außer die vermeintlich unnötigen Vergleiche). Gerade dann, wenn schon eine sortierte Liste vorliegt, brauchen diese Algorithmen trotzdem immer ihre quadratische Laufzeit, obwohl sie effektiv nichts machen. Abhilfe schafft hier Insertionsort, was im optimalen Fall, nämlich der bereits sortierten Liste, nur einmal komplett durchläuft und feststellt, dass die Liste sortiert ist. Somit hat dieses Verfahren im besten Fall lineare Laufzeit. Nur im schlimmsten Fall (umgekehrt sortierte Liste) benötigt das Verfahren auch quadratische Laufzeit. Aber wie funktioniert dieses Verfahren jetzt?

Insertionsort fängt immer an der zweiten Position an, wobei angenommen wird, das alles was davor ist, sortiert ist. Nun wird das aktuell betrachtete Element immer in diesen sortierten Bereich gezielt eingefügt. Im Fall einer Liste geschieht dies durch das umhängen von Pointern. Im Falle eines Arrays muss das Element so lange nach vorne getauscht werden, bis es an der richtigen Stelle steht. Um diese richtige Stelle zu finden, muss man jetzt aber nicht immer bis ganz nach vorne laufen. Da alles davor schon sortiert ist, muss man nur dann noch weiter nach vorne laufen, wenn das Element vor dem aktuell betrachteten, größer ist als das aktuelle. Im Fall einer Vorsortierten Liste, wird dies also nie auftreten und das erklärt die lineare Laufzeit. Schauen Sie sich auch hier wieder das entsprechende Beispiel an.

Veranschaulichung des Insertionsort Sortierverfahrens

Zuerst wird die 1 betrachtet und so lange nach vorne gelaufen, bis ein Element gefunden wird, welches nicht mehr größer ist. Die 6 ist größer und da vor ihr kein Element mehr kommt, also auch kein Element mehr größer ist, wird die 1 vorne eingefügt.

Im zweiten Schritt wird jetzt die 7 betrachtet und es wird festgestellt, dass das davor stehende Element kleiner ist, woraus zu schlussfolgern ist, dass davor nur noch kleinere Elemente kommen und die 7 somit schon an der richtigen Stelle steht.

Jetzt wird die 2 betrachtet und wieder fast bis ganz vorne verschoben, wobei alle Elemente dazwischen nach rutschen. Die 5 kommt dann anschließend zwischen 2 und 6 und so geht das Spiel weiter bis zum Ende.

Wie Sie sehr schön sehen können, braucht man im Durchschnitt sogar nur noch ein wenig mehr als die Hälfte des sortierten Bereiches zu durchlaufen und somit auch nur noch die Hälfte an Vergleichen. Somit ist Insertionsort in dieser Kategorie der klare Sieger.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012