Der Begriff Selectionsort bezeichnet einen naiven Sortieralgorithmus, der in-place arbeitet und in seiner Grundform instabil ist, wobei er sich auch stabil implementieren lässt. Die Komplexität von Selectionsort ist in der Landau-Notation so ausgedrückt: O(n²).

Alternative Bezeichnungen des Algorithmus sind MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort).

Selection = sortieren
in-place = Der Algorithmus überschreibt die Eingabedaten mit den Ausgabedaten.
Landau-Nation = asymptotische Verhalten von Funktionen und Folgen zu beschreiben.
O = Laufzeit Komplexität, Ordnung.

Die Funktionsweise von Selectionsort stellt sich so dar: Man hat ein Array in dem sich die zu sortierenden Daten befinden. Nun teilt man das Array im Geiste in zwei Teile. Der erste Teil soll den sortierten Teil darstellen, der zweite Teil den unsortierten. Da am Anfang noch nichts sortiert ist, stellt dementsprechend das gesamte Array den unsortierten Teil dar.

Nun sucht man das kleinste Element im Array und vertauscht es mit dem ersten Element. Nun befindet sich also das erste Element im sortierten Bereich und die restlichen Elemente im unsortierten. Nun wird wieder im unsortierten Teil nach dem kleinsten Element gesucht und dieses nun hinter dem ersten Element im sortierten Bereich eingefügt. Dies geht so lange, bis alle Elemente im sortierten Bereich und keins mehr im unsortierten Bereich sich befindet. Wer nach der Größe sortieren will, angefangen mit dem größten Element, sucht statt dem kleinsten, immer nach dem größten Element.

Selectionsort

Erklärung