Insertion Sort

Insertion Sort Erklärung

Was genau bedeutet denn nun Insertion Sort? Insertion Sort ist ein Algorithmus, der eine Datenmenge sortiert, indem er sie von vorn bis hinten durchgeht, die Elemente vergleicht und bei Bedarf ein Element entnimmt und weiter vorn wieder einsetzt.

Insertion Sort Funktionsweise

Wie funktioniert Insertion Sort? Grundsätzlich geht der Algorithmus die gesamte Menge an Elementen durch. Dabei gilt die Menge vor dem aktuellen Laufindex als sortiert, und die Menge nach dem Index als unsortiert.

Das aktuelle Element wird dabei mit den vorhergehenden Elementen verglichen, bis die passende Stelle gefunden ist. An dieser Stelle wird das Element dann eingefügt. Es kann aber auch sein, dass das Element bereits an seiner richtigen Position war.

In beiden Fällen geht es mit dem nächsten Element weiter, solange noch als unsortiert geltende Elemente vorhanden sind.

Insertion Sort Beispiel

Am besten lässt sich die Funktionsweise von Insertion Sort an einem Beispiel demonstrieren. Gegeben sei eine Menge von Zahlen [7, 3, 9, 2, 1, 4], die aufsteigend sortiert werden soll.

Das erste Element in der Menge kann grundsätzlich übersprungen werden, da es kein vorheriges Element gibt, mit dem es verglichen werden könnte.

Wie Du siehst, durchläuft der Algorithmus also die Menge von vorn bis hinten und schaut in diesem Fall, ob das aktuelle Element kleiner ist als die vorherigen Elemente. Dann schiebt er dieses Element weiter nach vorne, wenn nötig.

Insertion Sort Struktogramm

Durch das folgende Struktogramm wird die Funktionsweise und der Ablauf von Insertion Sort noch einmal besser verdeutlicht. Es liefert außerdem die Grundlage für eine mögliche Implementierung.

Abb. 1 - Insertion Sort Struktogramm

Insertion Sort Komplexität

Was den zusätzlich benötigten Speicherplatz angeht, ist der Algorithmus sehr effizient.

Das Sortieren der Elemente geschieht in-place. Außer den benötigten Hilfsvariablen wird nichts zwischengespeichert, sodass der benötigte Platz unabhängig von der zu sortierenden Mengengröße ist. Die Platzkomplexität ist also konstant und beträgt hier O(1).

Doch wie sieht es mit der Zeitkomplexität aus?

Insertion Sort Laufzeit

Du siehst bereits an dem oberen Beispiel, dass der Algorithmus mit zwei ineinander verschachtelten Schleifen arbeitet. Die erste Schleife durchläuft die Menge von vorn bis hinten. Die zweite Schleife vergleicht das aktuelle Element mit allen vorherigen Elementen, bis der passende Platz dafür gefunden ist.

Du siehst an dem Beispiel auch, dass die zweite Schleife bis ganz an den Anfang der Menge zurücklaufen muss, wenn das zu sortierende Element das bisher kleinste ist. Das kann bei großen und unsortierten Mengen schnell ineffizient werden.

Die beiden Schleifen haben jeweils eine Zeitkomplexität von O(n), weshalb sich für den Algorithmus eine Gesamtkomplexität von O(n²) ergibt.

Insertion Sort – Weitere Begrifflichkeiten

Zum Verständnis von Insertion Sort und dem Vergleich mit anderen Sortieralgorithmen werden im Folgenden noch weitere Begrifflichkeiten erklärt.

Insertion Sort stabil – instabil

Insertion Sort verändert die Anordnung der Elemente nur, wenn sich das zu sortierende Element tatsächlich unterscheidet. Wenn es gleich groß ist wie ein vorstehendes Element, wird es nicht verschoben.

Damit bleibt die Anordnung gleich großer Elemente immer erhalten. Insertion Sort ist also ein stabiler Sortieralgorithmus.

Insertion Sort vergleichsbasiert

Insertion Sort gehört zu den vergleichsbasierten Sortieralgorithmen. Der Algorithmus vergleicht also immer zwei Elemente miteinander, um über die Anordnung in der Datenmenge zu entscheiden.

Insertion Sort iterativ – rekursiv

Normalerweise implementiert man Insertion Sort iterativ, aber auch eine rekursive Implementierung ist möglich. Diese eignet sich jedoch mehr für Übungszwecke, denn es ist zu bedenken, dass bei der rekursiven Variante die Platzkomplexität des Algorithmus O(n) beträgt statt O(1).

Insertion Sort Parallelisierbarkeit

Der Insertion Sort Algorithmus ist nicht vollständig parallelisierbar.

Es gibt allerdings den Sortieralgorithmus Shellsort, der eine Erweiterung von Insertion Sort darstellt. Dieser ist zwar parallelisierbar, allerdings hat er nicht mehr die stabile Eigenschaft von Insertion Sort.

Insertion Sort Zusammenfassung

In der folgenden Tabelle findest Du die wichtigsten Eigenschaften von Insertion Sort übersichtlich zusammengefasst.

Insertion Sort Vorteile – Nachteile

Wie jedes andere Sortierverfahren hat auch Insertion Sort seine Vor- und Nachteile.

Das Problem des Insertion Sort Sortieralgorithmus zeigt sich schnell, wenn man mit großen und nicht vorsortierten Datenmengen arbeitet. Der Algorithmus arbeitet ineffizient, weil er eine große Anzahl an Vergleichen benötigt und weit über die Datenmenge iterieren muss. Das zeigt sich an der kostenintensiven, quadratischen Laufzeit im Worst-Case-Szenario.

Insertion Sort Pseudocode

Zum Abschluss findest Du hier noch eine Implementierung von Insertion Sort in Pseudocode.

function InsertionSort (List items)
    // Iteriere von vorn bis hinten durch die Liste.
    for i = 0 to items.length - 2 do:
        nextIndex = i + 1
        // Dieses Element wird mit den vorigen in der Liste verglichen.
        nextElem = items[nextIndex]
        
        // Schiebe alle vorigen Elemente so lange nach vorne, bis der richtige Platz für nextElem gefunden ist.
        while nextIndex > 0 AND nextElem < items[nextIndex - 1] do:
            items[nextIndex] = items[nextIndex - 1]
            nextIndex -= 1

        // Füge nextElem an der passenden Stelle ein.
        items[nextIndex] = nextElem

Wie Du siehst, ist die Implementierung von Insertion Sort nicht besonders aufwendig und relativ leicht verständlich.