Selectionsort

Ähnlich wie beim Insertionsort gibt es beim Selectionsort einen sortierten und unsortierten Bereich.

Am Anfang besteht das gesamte Array aus dem unsortierten Bereich. Dann wird nach dem kleinsten Element gesucht und dieses an den Anfang gesetzt (dadurch wird dieses Element zum sortierten Bereich).

Danach wird wieder im unsortierten Bereich nach dem kleinsten Element gesucht. Wenn das nächst kleinste Element gefunden wurde, wird dies an den sortierten Bereich angehängt. Dies wird solange wiederholt bis alle Elemente sortiert worden sind.

Der worst-case beim Selectionsort ist ein umgekehrt sortiertes Zahlenfeld, dennoch ist der Selectionsort nach der Hälfte des Durchlaufs bereits fertig alle Elemente zu sortieren.

(Quelle: Wikipedia: SelectionSort)

Quelltext

Ein möglicher Selectionsort ist im folgenden dargestellt.

for(int j = 0;j < zahlenfeld.length; j++){
            int kleinsterIndex = j;
            int kleinstes = zahlenfeld[j];    
            for(int i = j+1;i<zahlenfeld.length;i++){
                if(zahlenfeld[i] < kleinstes){
                    kleinsterIndex = i;
                    kleinstes = zahlenfeld[i];
                }
            }
            int speicher = zahlenfeld[j];
            zahlenfeld[j] = kleinstes;
            zahlenfeld[kleinsterIndex] = speicher;
        }