Der Selection-Sort-Algorithmus

Bubble Sort tauscht bei jedem Durchlauf Nachbarn, und Insertion Sort schiebt Elemente zur Seite, um Platz für jeden neuen Wert zu schaffen. Selection Sort verfolgt den direktesten Ansatz der drei: Für jede Position wird der kleinste verbleibende Wert in der gesamten Liste gesucht und direkt an seine Stelle getauscht.

Die Idee

Wie Insertion Sort hält Selection Sort einen sortierten Präfix am Anfang der Liste. Aber statt jedes neue Element dort einzufügen, wo es zwischen seinen Nachbarn hingehört, durchsucht es den gesamten unsortierten Rest nach dem Gesamtminimum und platziert dieses Minimum dann mit einem einzigen Tausch direkt am Ende des sortierten Präfix.

Das macht die beiden Arbeitshälften im Vergleich zu den anderen beiden Algorithmen asymmetrisch: Das Finden des Minimums braucht einen vollständigen Scan des Rests, aber das Platzieren kostet genau einen Tausch — nie mehr, egal wie weit es von seinem Platz entfernt war.

Implementierung

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

const int N = 20;
int values[N];
int i = 0;
int j = 1;
int minIdx = 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 comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (j <= N - 1) {
            if (values[j] < values[minIdx]) {
                minIdx = j;
            }
            j++;
        } else {
            if (minIdx != i) {
                int tmp = values[i];
                values[i] = values[minIdx];
                values[minIdx] = tmp;
            }
            i++;
            if (i >= N - 1) {
                done = true;
            } else {
                minIdx = i;
                j = i + 1;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (!done && idx == minIdx) {
            PlotColor(220, 60, 60);   // smallest value found so far this pass
        } 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 das Ende des sortierten Präfix, wie beim Insertion-Sort-Sample. j scannt vorwärts durch den unsortierten Rest auf der Suche nach einem kleineren Wert als dem aktuellen minIdx; sobald j am Ende angekommen ist, wird der Wert bei minIdx an Position i getauscht und der nächste Durchlauf beginnt. Wie zuvor führt frame() nur alle paar Aufrufe einen solchen Schritt aus, und nur das laufende Minimum wird hervorgehoben — der Scan-Zeiger j bewegt sich ohne eigene Farbe durch den blauen Bereich, da für den nächsten Tausch nur der Minimum-Kandidat zählt.

• grün — der sortierte Präfix, Werte bereits an ihrer finalen Position
• rot — der bisher kleinste gefundene Wert in diesem Durchlauf
• blau — in diesem Durchlauf noch nicht gescannt

Schritt für Schritt durchgerechnet

Für [5, 1, 4, 2, 8] durchsucht der erste Durchlauf die gesamte Liste nach dem Minimum:

Der Scan endet mit minIdx = 1, also werden values[0] und values[1] getauscht: [1, 5, 4, 2, 8]. Der nächste Durchlauf durchsucht nur noch [5, 4, 2, 8] nach seinem Minimum (2), tauscht es an Index 1, und so weiter — jeder Durchlauf verkleinert den unsortierten Rest um eins und kostet genau einen Tausch.

Warum die Anzahl der Tausche zählt

Selection Sort ist insgesamt O(n²), nicht besser als Bubble oder Insertion Sort — die Suche nach dem Minimum kostet weiterhin O(n) pro Durchlauf, bei n Durchläufen. Was ihn auszeichnet: Er führt höchstens n - 1 Tausche insgesamt aus, einen pro Durchlauf, egal wie durcheinander die Eingabe ist. Bubble Sort und Insertion Sort können jeweils bis zu O(n²) Tausche oder Verschiebungen bei einer schlecht sortierten Liste ausführen.

Diese Eigenschaft war früher wichtiger als heute: Auf Hardware, wo ein Tausch viel teurer ist als ein Vergleich — Schreiben in langsamen Speicher, oder Flash-Speicher mit begrenzter Anzahl an Schreibzyklen — ist die begrenzte Schreibanzahl von Selection Sort ein echter Vorteil, selbst bei gleichen O(n²)-Vergleichskosten. Anders als die anderen beiden ist er außerdem nicht stabil: Ein weit entferntes Minimum an seine Stelle zu tauschen kann es an gleichwertigen Elementen vorbeibefördern und damit ihre relative Reihenfolge ändern.

Fazit

Alle drei einfachen Sortierverfahren leisten O(n²) Arbeit, aber sie verteilen sie unterschiedlich: Bubble Sort durchsucht und tauscht Nachbarn wieder und wieder, Insertion Sort schiebt Elemente, um eine Lücke zu öffnen, und Selection Sort scannt einmal pro Durchlauf und committet sich auf einen einzigen Tausch. Die drei nebeneinander zu vergleichen zeigt gut, dass "gleiche asymptotische Komplexität" nicht "gleicher Algorithmus" bedeutet — die Konstanten, das Zugriffsmuster und Eigenschaften wie Stabilität hängen weiterhin davon ab, welchen man wählt.