Fachkonzept: InsertionSort

InsertionSort

Der Sortieralgorithmus InsertionSort sortiert eine Liste, indem er in jedem Schritt

das erste Element des unsortierten Bereichs nimmt und dieses
in den bereits sortierten Bereich an der passenden Stelle einfügt.

In den beiden Videos unten sieht man mehrere Marker (blaue Kreise unter den Balken).

Der blaue Marker markiert, bis zu welchem Element die Liste bereits sortiert ist und welches Element gerade eingefügt wird.
Der gelbe Marker markiert, an welcher Stelle das aktuelle Element in den bereits sortierten Bereich eingefügt werden muss.
Die beiden grünen Marker markieren, welche Elemente gerade miteinander verglichen werden.
Die beiden roten Marker markieren, welche Elemente gerade miteinander vertauscht werden.

InsertionSort mit 25 Elementen

InsertionSort mit 100 Elementen

Struktogramm InsertionSort

Java-Code InsertionSort

Sort_InsertionSort.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int sortiertBisIndex = 2;
 
while (sortiertBisIndex < daten.length) {
  int neuesElement = daten[sortiertBisIndex];
 
  for (int index = 0; index < sortiertBisIndex; index++) {
    if (neuesElement < daten[index]) {
      int temp = daten[sortiertBisIndex];
      daten[sortiertBisIndex] = daten[index];
      daten[index] = temp;
    }
  }
 
  sortiertBisIndex++;
}
 
printArray(daten);