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).

5	7	0	3	4	2	6	1	(0)
5	7	0	3	4	2	6	1	(0)
0	5	7	3	4	2	6	1	(2)
0	3	5	7	4	2	6	1	(2)
0	3	4	5	7	2	6	1	(2)
0	2	3	4	5	7	6	1	(4)
0	2	3	4	5	6	7	1	(1)
0	1	2	3	4	5	6	7	(6)

Pseudo Code

Der Algorithmus sieht im Pseudocode so aus: <syntaxhighlighting> 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 </syntaxhighlighting>