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 i1 an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[1] mit f[i1]
- Man suche im Feld f[2] bis f[N] die Position i2 an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[2] mit f[i2]
- Man verfahre wie oben weiter für Position i3 bis iN-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 i1=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 i2=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 i3=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 Mmin(N), der maximale Aufwand Mmax(N) und er mittlere Aufwand Mmit(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:
