Der Insertion-Sort-Algorithmus

Bubble Sort sortiert, indem es wiederholt die gesamte Liste durchläuft und Nachbarn tauscht. Insertion Sort verfolgt einen anderen Ansatz: Er hält vorne in der Liste einen sortierten Abschnitt und lässt ihn Element für Element wachsen, wobei jeder neue Wert genau dort eingefügt wird, wo er hingehört — so, wie die meisten Menschen ein Blatt Spielkarten sortieren.

Die Idee

Insertion Sort betrachtet die Liste als zweigeteilt: einen sortierten Präfix am Anfang und den Rest. Zu Beginn besteht der sortierte Präfix nur aus dem ersten Element — ein einzelnes Element ist trivial "sortiert".

Für jedes folgende Element, den Schlüssel, schiebt Insertion Sort es in den sortierten Präfix hinein: Es vergleicht den Schlüssel von rechts nach links mit dem Präfix und schiebt jedes größere Element eine Position nach rechts, bis es die Stelle findet, an die der Schlüssel gehört. Genau in die dabei entstehende Lücke wird der Schlüssel platziert. Danach ist der sortierte Präfix um eins gewachsen, und der Vorgang wiederholt sich mit dem nächsten Element.

Implementierung

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int i = 1;     // index of the element currently being inserted
int k = -2;    // -2 = pick a new key, -1..i-1 = shifting comparison pointer
int key = 0;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual shifts stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (k == -2) {
            if (i >= N) {
                done = true;
            } else {
                key = values[i];
                k = i - 1;
            }
        } else if (k >= 0 && values[k] > key) {
            values[k + 1] = values[k];
            k--;
        } else {
            values[k + 1] = key;
            i++;
            k = -2;
        }
    }

    PlotBackground(250, 250, 250);

    int activeIndex = (k == -2) ? i : (k + 1);
    int barWidth = plot_width / N;

    for (int idx = 0; idx < N; idx++) {
        if (!done && idx == activeIndex) {
            PlotColor(220, 60, 60);   // the key currently being inserted
        } else if (idx < i) {
            PlotColor(70, 170, 90);   // sorted prefix
        } else {
            PlotColor(30, 100, 200);  // not yet reached
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

i markiert, wie weit der sortierte Präfix reicht; k läuft rückwärts durch ihn und vergleicht mit key, wobei Elemente nach rechts geschoben werden (values[k + 1] = values[k]), solange sie größer sind. Sobald k keine größeren Elemente mehr zum Schieben findet, wird key in die Lücke geschrieben und i rückt vor. Wie beim Bubble-Sort-Sample führt frame() nur alle paar Aufrufe einen solchen Schritt aus, damit die einzelnen Verschiebungen sichtbar bleiben statt sofort durchzulaufen. Die Balkenfarben markieren dieselben drei Zustände wie zuvor, nur mit anderer Bedeutung:

• grün — der sortierte Präfix
• rot — der Schlüssel, der gerade eingefügt wird
• blau — noch nicht erreicht

Schritt für Schritt durchgerechnet

Für [5, 1, 4, 2, 8] beginnt der sortierte Präfix als nur [5]. Beim Einfügen von 1:

Der Präfix ist jetzt [1, 5]. Beim nächsten Einfügen von 4 reicht eine Verschiebung (5 rückt nach rechts, 4 landet zwischen 1 und 5); das Einfügen von 2 braucht zwei Verschiebungen vorbei an 5 und 4; 8 braucht keine, da es bereits größer ist als alles im Präfix. Nach allen vier Einfügungen ist die Liste sortiert.

Warum er manchmal noch verwendet wird

Insertion Sort ist im schlechtesten Fall O(n²), genau wie Bubble Sort — asymptotisch nicht besser. Aber zwei Eigenschaften halten ihn im praktischen Einsatz:

• Bester Fall O(n): Ist die Liste bereits sortiert oder fast sortiert, braucht jeder Schlüssel nur einen Vergleich, um festzustellen, dass keine Verschiebung nötig ist. Die naive Version von Bubble Sort hat diese Eigenschaft nicht; Insertion Sort bekommt sie geschenkt, weil es in diese Richtung vergleicht.
• Gut bei kleinen Eingaben: Bei kurzen Arrays (grob unter 10–20 Elementen, je nach System) schlägt der geringe Overhead pro Vergleich von Insertion Sort die Setup-Kosten rekursiver Divide-and-Conquer-Sorts. Deshalb wechseln Produktions-Implementierungen — Timsort, Introsort und die meisten std::sort-Implementierungen — zu Insertion Sort, sobald eine rekursive Partition unter eine kleine Größenschwelle schrumpft, statt bis ganz nach unten zu rekursieren.

Er ist außerdem ein stabiles Sortierverfahren: Elemente, die als gleich verglichen werden, behalten ihre ursprüngliche relative Reihenfolge, da ein Schlüssel immer nur an strikt kleineren Elementen vorbeigeschoben wird. Bubble Sort teilt diese Eigenschaft; nicht jeder Sortieralgorithmus tut das.

Fazit

Während Bubble Sort die gesamte Liste immer wieder neu durchsucht, setzt Insertion Sort auf einen wachsenden sortierten Bereich und verrichtet genau die Arbeit, die nötig ist, um jedes neue Element dort einzufügen. Dieser Unterschied — asymptotisch irrelevant, da beide O(n²) sind — macht in der Praxis viel aus, weshalb Insertion Sort, anders als Bubble Sort, auch heute noch in den Standard-Sortieralgorithmen auftaucht.