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 = 1; 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);