Insertion Sort

Stelle Dir vor, Du erhältst bei einem Kartenspiel 10 Karten auf die Hand. Wie würdest Du sie sortieren?

Die meisten Menschen würden einfach links beginnen, Karte für Karte durchgehen und diese weiter vorn einsortieren, wenn nötig. Und damit bist Du schon mittendrin im Thema, denn Insertion Sort macht im Grunde nichts anderes.

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 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.