Insertionsort


Beim Insertionsort-Algorithmus geschieht das Sortieren durch Einfügen. Vorzustellen ist sich dieser Algorithmus, wie die meisten Menschen Spielkarten in einer Hand sortieren. Vergleich man beispielsweise 10 Karten und möchte diese aufsteigend der Wertigkeit anordnen. Dann vergleicht man erst einmal die erste (ganz linke Karte) mit der zweiten Karte und falls die zweite Karte einen niedrigeren Wert hat, tauscht man sie mit der ersten Karte. Nun wird die zweite Karte mit der dritten Karte verglichen. Stimmt die Reihenfolge, dann wird anschließend die dritte Karte mit der vierten Karte verglichen. Hat die vierte Karte nun wiederum eine niedrigere Wertigkeit, werden die beiden Karten getauscht. Anschließend muss überprüft werden, ob die nun neue dritte Karte auch größer ist als die zweite Karte, falls nicht werden die beiden getauscht und es muss wieder überprüft werden, ob die neue zweite Karte größer als die erste Karte ist. Falls ja, dann bleibt sie an der Stelle zwei und es kann nun die vierte Karte mit der fünften verglichen werden usw.

Grafisches Beispiel:

Im nachfolgenden grafischen Beispiel wird Insertionsort noch einmal dargestellt. Dabei sind die blau unterlegten Felder immer die Felder, die im aktuellen Schritt verglichen werden. Die Pfeile zeigen darüber hinaus, falls es im aktuellen Schritt zu einem Austausch der Felder kommt.
Beispiel des Insertionsort Algorithmus

Pseudocode von Insertionsort

Anbei der Pseudocode von Insertionsort, der noch einmal die Vorgehensweise des Algorithmus verdeutlichen soll und mit jeder Programmiersprache umgesetzt werden kann.

for i = 2 to eingabe.länge
	einzusortierender_wert = eingabe[i]
	j = i - 1
	while j > 0 und eingabe[j] > einzusortierender_wert
		eingabe[j+1] = eingabe[j]
		j = j - 1
	eingabe[j+1] = einzusortierender_wert
	

Wie man aus dem Pseudocode erkennen kann, wäre eine Schleifeninvariante von Insertionsort, dass das Teilfeld eingabe[1...i-1] immer die ursprünglich in eingabe[1...i-1] enthaltene Elemente enthält, allerdings in sortierte Reihenfolge.


Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972