Insertion Sort

6.1 Definition des Insertion Sort

Insertion Sort ist ein Sortieralgorithmus, der ein sortiertes Array (oder eine Liste) aufbaut, indem er ein Element nach dem anderen einsortiert. Er nimmt jedes Element aus dem unsortierten Teil und platziert es an der richtigen Position im sortierten Teil.

Funktionsweise:

1. Wir beginnen mit dem zweiten Element des Arrays (das erste Element wird als sortiert betrachtet).
2. Wir vergleichen das aktuelle Element mit den vorherigen und verschieben es nach links, bis wir die richtige Stelle finden.
3. Wir wiederholen den Vorgang für alle Elemente des Arrays und platzieren jedes neue Element an der richtigen Stelle im bereits sortierten Teil des Arrays.

Zeit- und Platzkomplexität des Insertion Sort

Zeitkomplexität:

• Im schlimmsten Fall: O(n^2) — tritt auf, wenn die Elemente ursprünglich in umgekehrter Reihenfolge vorliegen.
• Im Durchschnittsfall: O(n^2) — tritt bei zufälliger Anordnung der Elemente auf.
• Im besten Fall: O(n) — tritt auf, wenn die Elemente bereits sortiert sind.

Platzkomplexität:

O(1) — da der Algorithmus eine konstante Menge an zusätzlichem Speicher verwendet (nur ein paar Variablen zur Speicherung temporärer Werte).

6.2 Analyse des Algorithmus

Im nächsten Schritt des Algorithmus haben wir die folgende Situation:

• Wir haben ein aktuelles Element mit dem Index i.
• Alle Elemente links von ihm sind bereits sortiert von klein nach groß.
• Wir versuchen, unser aktuelles Element in den sortierten Teil des Arrays einzufügen, ohne die Sortierreihenfolge zu verletzen.

Der Versuch, ein Element in den sortierten Teil des Arrays einzufügen, sieht so aus:

1. Die Variable j im Schleifendurchlauf nimmt Werte von i - 1 bis 0 an.
2. Wenn das aktuelle (i-te) Element kleiner als das j-te ist, verschieben wir das j-te Element um 1 nach rechts.

Beispiel: aktuelle Situation:

• Grün markiert sind bereits sortierte Elemente.
• Rosa markiert sind die Elemente, die noch nicht sortiert wurden.
• Das aktuelle Element mit dem Index 5 ist braun markiert.

Wir versuchen, das passende Plätzchen für unser aktuelles Element im sortierten Teil des Arrays zu finden.

Schritt 1 — Wir merken uns den Wert des aktuellen Elements in der Variable key.

Schritt 2 — Ist Element No4 größer als key? (10 größer als 5?) Dann verschieben wir das Element No4 nach rechts:

Schritt 3 — Ist Element No3 größer als key? (8 größer als 5?) Dann verschieben wir das Element No3 nach rechts:

Schritt 4 — Ist Element No2 größer als key? (6 größer als 5?) Dann verschieben wir das Element No2 nach rechts:

Schritt 5 — Ist Element No1 größer als key? (4 größer als 5?) Nein. Dann speichern wir das Element key an der Stelle, an der vorher das Element No2 war.

Nachdem wir das Element No5 an die richtige Stelle eingefügt haben, wechseln wir zum Element No6 und versuchen, ihm einen Platz im sortierten Teil des Arrays zuzuweisen:

Dann nehmen wir das siebte Element:

Dann das 8.:

6.3 Implementierung des Insertion Sort Algorithmus

So sieht dieser Algorithmus in Python aus:

def insertion_sort(arr):
    # Wir gehen alle Elemente des Arrays durch, beginnend mit dem zweiten
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Wir verschieben alle Elemente arr[0..i - 1], die größer als der Schlüssel sind, um eine Position nach vorne
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Wir fügen den Schlüssel an der richtigen Stelle ein
    return arr  # Wir geben das sortierte Array zurück

# Beispiel der Nutzung:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sortiertes Array:", sorted_arr)
# Ausgabe: Sortiertes Array: [5, 6, 11, 12, 13]

Erklärung:

• Wir speichern das aktuelle Element in key
• Wir verschieben alle Elemente des sortierten Teils des Arrays nach rechts
• Wir fügen unser Element an der passenden Stelle ein

Beispiel der Arbeitsweise des Algorithmus

Wir nehmen das Beispielarray: [12, 11, 13, 5, 6]

1. Erster Durchgang (i = 1):

• Wir vergleichen 11 und 12, verschieben 12 nach rechts.
• Array: [11, 12, 13, 5, 6]

2. Zweiter Durchgang (i = 2):

• 13 ist bereits an der richtigen Stelle.
• Array: [11, 12, 13, 5, 6]

3. Dritter Durchgang (i = 3):

• Wir vergleichen 5 mit 13, 12 und 11, verschieben alle nach rechts.
• Array: [5, 11, 12, 13, 6]

4. Vierter Durchgang (i = 4):

• Wir vergleichen 6 mit 13, 12 und 11, verschieben alle nach rechts.
• Array: [5, 6, 11, 12, 13]

Der Algorithmus endet, da alle Elemente sortiert sind.