Sortieralgorithmen/ Insertionsort

Für das Sortierverfahren Insertionsort nehmen wir beliebige Zahlen als Beispiel. In diesem Sortierverfahren muss man sich eine Wand vorstellen, bei der links die sortierten und rechts die unsortierten Zahlen stehen. Zurzeit stehen alle, bis auf eine zufällig aus dem Zahlensystem gegriffene Zahl, rechts von der Mauer. Im nächsten Schritt rückt die Mauer um eine Stelle nach links. Das heißt, dass wir links von der Mauer nun zwei Zahlen stehen haben, einmal die Grundzahl (welche am Anfang zufällig aus dem Zahlensystem genommen wurde) und eine zweite Zahl (welche vor der Verrückung der Mauer auf der rechten Seite die Zahl war, die am nächsten an der Mauer war).

Ist die erste Zahl größer, als die zweite, wechseln die beiden Zahlen ihre Position miteinander, falls dies nicht der Fall ist. bleiben beide Zahlen so stehen und die Mauer rückt wieder eins nach rechts, wo eine dritte Zahl nun auf die linke Seite der Mauer verschoben wurde, welche wiederum erst mit der an zweiter und dann mit der an erster Stelle stehenden Zahl verglichen wird. Dieses Verfahren wird solange wiederholt, bis keine Zahl mehr auf der linken Seite der Mauer steht.

Insertionsort ist ein stabiles Verfahren, welches bei wenig zu sortierenden Elementen sehr effizient arbeitet. (7)

Sonst ist es aber insgesamt nicht so sehr effizient, wie manche besseren Sortierverfahren. Deutsch übersetzt bedeutet Insertionsort soviel wie Einfügsortierung, da es wie oben beschrieben die Zahlen an die richtige Stelle einfügt.

Da dieses Sortierverfahren in-place arbeitet, benötigt es keinen weiteren Speicherplatz.
Dieser Algorithmus wurde von D.L.Shell zu dem nicht stabilen Sortierverfahren Shellsort weiterentwickelt.

Um dieses Sortierverfahren bildhaft darzustellen beschreibe ich hier ein Beispiel aus dem echten Leben.

In einem Schuhladen werden verschieden große Schuhe verkauft. Als eine neue Lieferung Schuhe eintrifft, sollen diese der Größe nach sortiert werden. Diese Aufgabe wird einer Verkäuferin übertragen. Diese nimmt also das erste paar Schuhe (A) und sagt, dass dieses sortiert ist. Dann nimmt sie das zweite (B) und vergleicht es mit dem ersten. Da das zweite Paar Schuhe kleiner, als das Erste ist, legt sie es links neben dieses (A), so dass die Schuhe jetzt in der Reihenfolge liegen B, A. Dann nimmt sie das dritte (C) Paar vom unsortierten Stapel und vergleicht es mit den beiden anderen Schuhpaaren. Da es kleiner, als die zweiten Schuhe (A) ist, aber größer, als die ersten (B), kommt es zwischen die beiden. Dadurch liegen die Schuhe jetzt in dieser Reihenfolge B, C, A. Im nächsten Schritt nimmt die Verkäuferin das vierte Schuhpaar (D) vom unsortierten Stapel, vergleicht mit dem ersten, dem zweiten und dem dritten und fügt es an die richtige Stelle ein. Da das vierte Schuhpaar größer, als das dritte (A) ist, wird es rechts vom dritten einsortiert, so dass die Reihenfolge jetzt B, C, A, D ist.

Jetzt nimmt die Verkäuferin das fünfte und letzte Schuhpaar und vergleicht es mit dem vierten (D), da es kleiner ist, vergleicht sie es als nächstes mit dem dritten (A), da das fünfte Schuhpaar (E) auch hier kleiner ist, vergleicht sie es mit dem zweiten (C), da es hierbei aber größer ist, wird es zwischen diesem Schuhpaar und dem dritten einsortiert. Zum Schluss sind alle Schuhe der Größe nach sortiert und die Schuhpaarreihenfolge sieht nun also so aus B, C, E, A, D.