Gebrauch
Der Insertionsort wird gebraucht, um einen unsortierten Array zu sortieren.
Der Algorithmus ist vegleichbar mit dem, den von den meisten gebraucht wird, um Karten in der Hand zu sortieren.
Spezifikationen
Der Insertionsort Algorithmus hat eine worst-case Performance von O(n2) Vergleiche, O(n2) Tauschungen und eine best-case Performance von O(n) Vergleiche, O(1) Tauschungen. Seine Durchschnittsperformance beträgt O(n2) Vergleiche, O(n2) Tauschungen.
Der Algorithmus braucht keine weiteren Arrays und hat somit jeweils eine Space-complexity von O(1).
Funktionsweise
Der Algorithmus wird Insertionsort genannt, da jeweils ein Wert in den sortierten Subarray eingefügt (engl. insert) wird.
Bei dem Insertionsort wird mit dem Wert an der Stelle des tiefsten Indexes begonnen. Das Grundprinzip basiert darauf, dass der Subarray von Index 0 bis, aber ohne, den fokussierten Wert automatisch sortiert ist und den fokussierten Wert schliesslich in die richtigen Stelle des sortierten Subarrays einfügt, indem er mit jedem Wert des sortierten Subarrays verglichen wird. Schlussendlich wird mit dem kleinstmöglichen Index, welcher nicht sortiert ist, fortgefahren.
Der fokussierte Wert wird mit jedem in dem sortierten Subarray verglichen, indem überprüft wird, ob der Wert dessen Index kleiner ist als der, des fokussierten, grösser ist, als der fokussierte Wert. Falls dies der Fall ist,
Der Array ist sortiert, sobald der Wert am letzten Index an der korrekten Stelle eingefügt wurde.
Beispielcode
Dies ist ein in Python geschriebener Beispielcode:
# arr ist der Array, welcher zu sortieren ist. Die Funktion gibt den sortierten Array zurück
def insertionSort(arr):
# Über alle Werte von Index 1 an werden iteriert, um an die richtige Stelle inserted zu werden
for i in range(1, len(arr)):
# Über alle Werte, dessen Index kleiner ist als der, des momentan fokussierten Wertes werden iteriert
for j in range(i - 1, -1, -1):
# Falls der Wert, welcher inserted wird grösser ist, als der, mit dem er verglichen wird
if arr[j] > arr[j + 1]:
# Switche die beiden Werte bei Index j und (j + 1) miteinander
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Fahre ansonsten fort mit dem Inserten des nächsten Wertes
else:
break
# Der sortierte Array wird zurückgegeben
return arr
Dies ist ein in Java geschriebener Beispielcode:
Es können selbstverständlich auch andere Datentypen gebraucht werden.
// arr ist der Array, welcher zu sortieren ist. Die Funktion gibt den sortierten Array zurück
public static int[] insertionSort(int[] arr) {
// Über alle Werte von Index 1 an werden iteriert, um an die richtige Stelle inserted zu werden
for (int i = 1; i < arr.length; i++) {
// Über alle Werte, dessen Index kleiner ist als der, des momentan fokussierten Wertes werden iteriert
for (int j = i - 1; j >= 0; j--) {
// Falls der Wert, welcher inserted wird grösser ist, als der, mit dem er verglichen wird
if (arr[j] > arr[j + 1]) {
// Switche die beiden Werte bei index j und (j + 1) miteinander
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
// Fahre ansonsten fort mit dem Inserten des nächsten Wertes
else break;
}
}
// Der sortierte Array wird zurückgegeben
return arr;
}
Animiertes Beispiel
Legende
- Fokussierter Wert
- Wert, mit dem der fokussierte Wert verglichen wird
- Momentan nicht beachteter Wert
- Wert am korrekten Index
Drücke Start, um die Animation zu starten. Ändere die Position des Sliders, um die Geschwindigkeit der Animation zu verändern.