Insertion Sort ( = sortieren durch direktes Einfügen ) funktioniert folgendermaßen :
Das Prinzip ist relativ einfache. Wir betrachten die ersten beiden Elemente und sortieren diese nach Ihrer Größe. Als nächstes betrachten wir die nächsten drei Elemente und sortieren diese nach Ihrer Größe. Als nächsten Schritt betrachten wir die ersten 4 Elemente und sortieren........ usw.

Bildlich können sie sich Insertion Sort folgendermaßen vorstellen.....

Versuchen sie dieses Bild Anhand des folgenden Quellcodes besser zu verstehen, falls nicht schon verstanden....

/*Download:insert.c*/ #include <stdio.h> void insertion(int array[], int elemente) { int i,j,temp; for(i=1; i<=elemente; i++) { temp=array[i]; /*aktuelles Element zwischenspeichern*/ for(j=i; array[j-1] > temp && j > 0; j--) array[j] = array[j-1]; /*Wenn Vorgänger größer als aktuelles Element in temp*/ array[j]=temp; /*gespeichertes Element an neue Position*/ } } int main() { int i; /*Unser Array zum sortieren*/ int test_array[] = { 5, 2, 7, 9, 1, 4, 3, 8, 6 }; int N = sizeof(test_array)/sizeof(int); insertion(test_array, N-1); for(i=0; i<N; i++) printf("%d ",test_array[i]); printf("\n"); return 0; }

Wie auch bei Selection Sort sind die Elemente beim Instertion Sort auf der linken Seite sortiert, nur mit dem Unterschied, daß dies noch keine endgültige Stellung wie beim Selection Sort bedeutet.