Sortieralgorithmen: Selection sort

Der Selection sort Algorithmus ist ein weiteres Verfahren zum aufsteigenden sortieren von Objekten. Im Gegensatz zum Bubble sort wird in diesem Verfahren zunächst das kleinste Element aus der Liste gesucht und als Index gespeichert. Wenn die komplette Liste durchlaufen wurde, dann wird das kleinste Element an der ersten Position der Liste verschoben. Somit ist das erste Element sortiert.

Die weiteren Schleifendurchläufe funktionieren genauso nur mit dem Unterschied, dass die bereits sortieren Indizes nicht mehr mit in die Berechnung einfließen.

Man kann sich das so vorstellen: Am Anfang hat man eine möglicherweise unsortierte Liste. Diese unsortierte Liste hat die Größe N. Mit jedem Durchlauf wird ein Element sortiert und die Größe der unsortierten Liste wird um eins verringert.
Am Ende des Verfahrens wurde die unsortierte Liste in eine sortierte Liste umgewandelt.

• Selection sort (c++)

#include <iostream>

void selectionSort(){
    const unsigned int SIZE = 10;
    int list[SIZE] = {4,1,6,3,5,5,12,9,8,7};
    
    unsigned int i = 0;
    unsigned int j = i;
    unsigned int minimum_idx = i;

    for(unsigned int i = 0; i < SIZE - 1; i++){
        minimum_idx = i;
        for(unsigned int j = i + 1; j < SIZE; j++){
            // Suche das kleinste Element im unsortierten Array
            if(list[j] < list[minimum_idx]){
                minimum_idx = j;
            }
                
            // Tausche den kleinsten Wert mit dem ersten Wert
            int tmp = list[minimum_idx];
            list[minimum_idx] = list[i];
            list[i] = tmp;
        }
    }
    
    for(unsigned int r = 0; r < SIZE; r++){
        std::cout << list[r] << "\n";
    }
    
}

int main(){
    selectionSort();
    return 0;
}

Quelle
https://www.researchgate.net/publication/265623392_Upgraded_Selection_Sort, pp. 1633f. [letzter Zugriff: 31.01.2020, 17:33]