Beim Suchen durch Auswahl durchsucht man das jeweilige Feld nach dem kleinsten Wert und tauscht den Wert an der gefundenen Position mit dem Wert an der ersten Stelle.

Anschließend sucht man ab der zweiten Position aufsteigend nach dem zweitkleinsten Wert und tauscht diesen Wert mit dem Wert der zweiten Position.

Man fährt entsprechend mit der dritten und allen weiteren Positionen fort bis alle Werte aufsteigend sortiert sind.

Verfahren

• Man suche im Feld f[1] bis f[N] die Position i₁ an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[1] mit f[i₁]
• Man suche im Feld f[2] bis f[N] die Position i₂ an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[2] mit f[i₂]
• Man verfahre wie oben weiter für Position i₃ bis i_N-1

Beispiel

Ausgangssituation: Ein Feld mit 7 unsortierten Ganzzahlwerten (N=7)

Die Zahl 12 auf Position 5 ist die kleinste Zahl im Feld f[1] bis f[7]. Somit ist i₁=5. Nach Vertauschen von f[1] mit f[5] ergibt sich:

Die Zahl 13 auf Position 4 ist die kleinste Zahl im Feld f[2] bis f[7]. Somit ist i₂=4. Nach Vertauschen von f[2] mit f[4] ergibt sich:

Die Zahl 18 auf Position 5 ist die kleinste Zahl im Feld f[3] bis f[7]. Somit ist i₃=5. Nach Vertauschen von f[3] mit f[5] ergibt sich:

Das Verfahren wird entsprechend weiter wiederholt bis alle Werte sortiert sind.

Aufwand

Der minimale Aufwand M_min(N), der maximale Aufwand M_max(N) und er mittlere Aufwand M_mit(N) ist bei diesem naiven Verfahren gleich, da immer die gleiche Anzahl von Operationen (N-1) ausgeführt wird. Der Faktor 3 ensteht dadurch, dass bei einer Vertauschung zweier Werte insgesamt drei Operationen braucht:

Die Anzahl der Vergleiche sind die Summe von n-1, n-1 etc. unabhängig davon ob das Feld sortiert oder unsortiert ist:

Implementierung

Die Implementierung der Klasse SelectionSort.java ist bei Github zu finden.