Insertion Sort

Der Insertion Sort ist neben dem Bubble Sort ein weiterer grundlegender Algorithmus. Er gehört zu den sogenannten „in situ“ bzw. „in place“ Sortieralgorithmen, da die Elemente innerhalb der Eingabeliste sortiert werden können.

Schauen wir uns ein Beispiel dazu an. Gegeben sei die Liste L = {28, 4, 78, 36, 5, 11} die wir jetzt mittels Insertion Sort sortieren möchten.

Beispiel zum Insertion Sort

Als Erstes wird die Liste nach dem ersten Element, also der 28, geteilt. Die 28 gilt hier als sortierter Bereich, während der Rest der Liste L entsprechend unsortiert ist. Die Trennung erfolgt auch nur symbolisch zum besseren Verständnis.

28 | 4 78 36 5 11

Als Nächstes untersuchen wir die 4. Wäre das Element jetzt größer als das erste, würde die 4 genau an der Stelle verbleiben. Da aber die 4 kleiner als die 28 ist, wird sie an erster Stelle in der Liste eingefügt.

4 28 | 78 36 5 11

Der vordere Teil ist nun korrekt sortiert. Nun verbleiben noch die restlichen Elemente der Liste. Jetzt folgt die 78 und das obige Szenario tritt ein. Die 78 ist größer als die 28. Da der linke Teil der Liste sortiert ist, muss die 78 auch nicht mehr mit der 4 verglichen werden. So kann die 78 also entsprechend an ihrem bisherigen Platz verbleiben.

4 28 78 | 36 5 11

Drei weitere Elemente sind noch übrig. Fahren wir mit der 36 fort. Verglichen mit der 78, ist die 36 eindeutig kleiner. Hierbei muss jetzt die 36 aber auch mit der 28 verglichen werden, um den korrekten Platz in der Liste zu finden. Da die 36 größer als die 28 ist, wird sie direkt danach eingefügt.

4 28 36 78 | 5 11

Das nächste Element ist die 5. Die ist definitiv kleiner als die 78, die 36, die 28 und größer als die 4. Also wird die 5 nach 4 eingefügt.

4 5 28 36 78 | 11

Als letztes Element bleibt uns nur noch die 11. Die 11 ist kleiner als die 78, 36, 28 und größer als die 5. So wird die 11 abschließend nach der 5 einsortiert und wir erhalten unsere vollständig sortierte Liste mittels Insertion Sort.

4 5 11 28 36 78

Wer sich für den Pseudocode interessiert, dem habe ich hier den Wikipedia-Artikel verlinkt.