Selection Sort

Selection Sort sucht im unsortierten Bereich das Minimum und tauscht es an die nächste Position. Nach i Schritten sind die ersten i Positionen final.

Immer $\Theta(n^{2})$ Vergleiche, wenige Vertauschungen (höchstens n).

Bibliothekssortierung zum Vergleich: Sort an Array [1].

Wo gebraucht

Nur Lehr- und Mikro-Fälle. Zeigt Auswahl-Idee; in Produktion durch bibliothekssortierer ersetzen.

Vertiefung

Selection Sort teilt das Array in einen sortierten Präfix und einen noch ungeordneten Rest. In Runde i wird im Rest ein kleinstes Element gesucht und an Position i gebracht. Danach enthält der Präfix genau die i plus eins kleinsten Werte, wenn Mehrfachwerte mitgezählt werden.

Die Suche nach dem Minimum betrachtet den verbleibenden Bereich unabhängig davon, wie vorsortiert die Eingabe ist. Die Zahl tatsächlicher Austauschoperationen bleibt dagegen an die Zahl der Runden gebunden und kann entfallen, wenn das Minimum bereits vorne liegt.

Schwierigkeitsstufen

1. Eine Runde mit Minimumindex und anschliessendem Tausch ausführen.
2. Die Präfixinvariante zur Korrektheit formulieren.
3. Vergleichs- und Schreibkosten getrennt beurteilen.

Fallstricke

Der gefundene Wert allein genügt nicht, weil für den Tausch sein Index benötigt wird. Bei mehrfachen Minima beeinflusst die Wahl des Vorkommens ausserdem die relative Ordnung gleicher Schlüssel.