Insertion-Sort

aus www.iwiki.de, der freien Wissensdatenbank

Insertion-Sort ist ein elementares Sortierverfahren.

Inhaltsverzeichnis

1 Prinzip
2 Beispiel
3 Implementierung
4 Weblinks

Prinzip

Beim Insertion-Sort besteht der sortierte Teil Anfangs aus einem Element. Bei jedem Durchgang wird aus dem unsortierten Teil das erste Element(U) genommen. Dieses wird mit dem letzten Element(S) aus der sortierten Liste verglichen. Ist S>U werden die beiden Elemente miteinander vertauscht (Bei Gleichheit passiert nichts). U wird solange mit den vorhergehenden Elementen verglichen, bis die richtige Position gefunden ist. Befindet sich U an der richtigen Stelle, wird der unsortierten Liste das nächste Element entnommen. Dieser Vorgang wiederholt sich, bis die Feldstruktur nur noch aus dem sortierten Teil besteht.

[bearbeiten]

Beispiel

[bearbeiten]

Implementierung

Insertionsort (int data[],int n) {
  int tmp,i,j;
  for (j=1; j<n; j++) {
      i =j - 1;
      tmp = data[j];
      while ( (i>=0) && (tmp < data[i]) ) {
          data[i+1] = data[i];
          i--;
      }
      data[i+1] = tmp;
  }
}

[bearbeiten]