Implementierung: Selection Sort Schritt

Implementiere das Finden des Minimumsindex in einem Teilarray.

Wo gebraucht

Kontrolliert, dass In-Place-Mutationen und Indexgrenzen sitzen, bevor man komplexere Partitionen angeht.

Vertiefung

Ein einzelner Selection-Sort-Schritt erhält einen Startindex. Er durchsucht den Bereich ab dort, merkt sich den Index des bisher kleinsten Elements und tauscht dieses nach Abschluss der Suche an den Start. Während der Schleife bezeichnet minIndex stets eine kleinste bisher untersuchte Position.

Die Schleife beginnt bei start plus eins, weil das Startelement bereits als vorläufiges Minimum gilt. Ein optionaler Tauschtest vermeidet Selbsttausch. Nach dem Schritt ist nur die Startposition garantiert korrekt, nicht der gesamte Restbereich.

Schwierigkeitsstufen

1. minIndex über einen Teilbereich aktualisieren.
2. Die Schleifeninvariante des Minimumscans angeben.
3. Den Schritt in die vollständige äussere Sortierschleife einbetten.

Fallstricke

Wer bei jedem kleineren Element sofort tauscht, implementiert einen anderen und schreibintensiveren Ablauf. Die Suche muss ausserdem den letzten Arrayindex einschliessen.