Sortieren durch Auswahl (Selection Sort)

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:

 

Selectionsort: Implementierung in Java

Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden ist.

Implementierung: Klasse Selectionsort

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class SelectionSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public SelectionSort(int[] s) {super(s,false);}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
@Override
public void sortieren(int startIndex, int endeIndex){
//geschwaetzig=true;
int minimumIndex;
for (int unteresEnde=startIndex; unteresEnde<endeIndex; unteresEnde++) {
minimumIndex = unteresEnde; //Vergleichswert
// Bestimme Position des kleinsten Element im Intervall
for (int j=unteresEnde+1; j<=endeIndex; j++) {
if (istKleiner(j,minimumIndex)) {
minimumIndex=j; // neuer Kandidat
}
}
// Tausche kleinstes Element an den Anfang des Intervalls
tausche(unteresEnde,minimumIndex);
// das kleinste Element belegt jetzt das untere Ende des Intervalls
}
}
/**
* Liefert den Namen des SelectionSorts
* @return
*/
@Override
public String algorithmus() {return "Sortieren durch Auswahl";}
}