Sortieren durch Auswahl (Selectionsort)

Sortieren durch Auswahl (Selectionsort)

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:

Implementierung

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

Stefan Schneider Wed, 01/19/2011 - 22:41

Anonymous (not verified)

Thu, 05/08/2014 - 14:12

Lautet das erste Element eines Feldes nicht f[0]?
Dann würde man dementsprechend ab der Position f[0] anfangen, das Feld zu durchsuchen!

Sehr gute Beobachtung,
Java fängt bei Null an zu zählen. Menschen beginnen oft bei Eins. Ich kann Ihnen da leider keine einfache Lösung bieten. Das ist Definitionssache. Man muß immer schauen was die Definition des ersten Elements ist.

Selectionsort: Implementierung in Java

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";}
}

 

Stefan Schneider Sun, 03/20/2011 - 00:16

Anonymous (not verified)

Mon, 06/20/2016 - 13:26

Wenn Sie

tausche(unteresEnde,minimumIndex);

zum Tauschen verwenden, brauchen wir keine Variable:

int temp; // Hilfsvariable zum Tauschen

.

Stefan Schneider

Mon, 06/20/2016 - 19:15

In reply to by Anonymous (not verified)

Variable wurde gelöscht.
Weniger Code.
Schnelleres Programm
Weniger Fehlerquellen
Einfacher zu verstehen.

Gut beobachtet. Danke