Fachinformatiker Prüfungsvorbereitung

Diese Webseite ist momentan nicht responsiv. Bitte öffnen Sie sie auf einem größeren Bildschirm.

Der Insertion Sort Algorithmus

Insertion Sort ist ein einfacher und intuitiver Algorithmus zur Sortierung von Daten. Er funktioniert ähnlich wie das Sortieren von Spielkarten: Indem jedes neue Element an die richtige Stelle eingefügt wird, entsteht schrittweise eine sortierte Liste. Dieser Algorithmus eignet sich besonders für kleine Datenmengen oder fast sortierte Listen.

Wie funktioniert Insertion Sort?

Der Algorithmus arbeitet, indem er die Liste in einen sortierten und einen unsortierten Teil aufteilt. Jedes Element aus dem unsortierten Teil wird nacheinander an der richtigen Position in den sortierten Teil eingefügt.

Beispiel:

Angenommen, wir möchten die Liste [7, 3, 5, 2] sortieren:

  1. Starte mit dem ersten Element: [7] ist bereits sortiert.
  2. Das zweite Element 3 wird eingefügt: [3, 7].
  3. Das dritte Element 5 wird an der richtigen Stelle eingefügt: [3, 5, 7].
  4. Das letzte Element 2 wird eingefügt: [2, 3, 5, 7].

Pseudocode für Insertion Sort

          Algorithm InsertionSort(array):
            for i from 1 to length(array) - 1 do:
                key = array[i]
                j = i - 1
                while j >= 0 and array[j] > key do:
                    array[j + 1] = array[j]
                    j = j - 1
                array[j + 1] = key

Erklärung des Pseudocodes

Der Pseudocode des Insertion Sort Algorithmus funktioniert wie folgt:

  • Zuerst wird der Algorithmus von `i = 1` bis zum Ende der Liste durchlaufen. Dabei wird das aktuelle Element, genannt key, aus dem unsortierten Teil der Liste entnommen.
  • Mit dem Index j wird der letzte Index des sortierten Teils der Liste referenziert. Dieser Wert wird von `i - 1` gesetzt.
  • Im while-Loop wird überprüft, ob das Element an Index `j` größer ist als das key-Element. Wenn ja, wird das Element an Index `j` nach rechts verschoben, und `j` wird um eins verringert.
  • Sobald das richtige Element gefunden ist, an dem das key-Element eingefügt werden soll, wird es an der richtigen Position in der sortierten Liste platziert, was durch die Zeile array[j + 1] = key geschieht.

Warum wird array[j + 1] = array[j] verwendet?

Wenn wir ein Element aus dem unsortierten Teil der Liste entnehmen (das key), müssen wir die größeren Elemente in der sortierten Liste nach rechts verschieben, um Platz für das key-Element zu schaffen. Dabei wird der Wert von array[j] in array[j + 1] verschoben. Das Element key bleibt jedoch gespeichert, sodass es später an der richtigen Position eingefügt werden kann.

Wann sollte Insertion Sort verwendet werden?

Insertion Sort ist besonders geeignet für:

  • Kleine Datensätze, da der Algorithmus einfach zu implementieren ist.
  • Fast sortierte Listen, da er hier sehr effizient arbeitet.

Vorteile und Nachteile

Vorteile:

  • Einfache Implementierung.
  • Effizient für kleine oder fast sortierte Listen.
  • Stabil: Die Reihenfolge gleicher Elemente bleibt erhalten.

Nachteile:

  • Langsam für große Datensätze.
  • Quadratische Zeitkomplexität: O(n²) im Worst Case.

Zeitkomplexität (Big-O-Notation)

Die Zeitkomplexität von Insertion Sort hängt davon ab, wie die Daten anfangs sortiert sind:

  • Best Case: O(n), wenn die Liste bereits sortiert ist.
  • Average Case: O(n²).
  • Worst Case: O(n²), wenn die Liste in umgekehrter Reihenfolge ist.