Selection Sort

Zuletzt haben wir in der Kategorie der Algorithmen den Insertion Sort behandelt. Wie der Name schon sagt sortiert der Selection Sort die unsortierte Liste L durch Auswählen des kleinsten Elements. Wie das genau aussieht, zeige ich wie immer an einem Beispiel.

Beispiel zum Selection Sort

Nehmen wir uns wieder eine Liste L = {35, 74, 6, 3, 14, 25}, die wir mittels Selection Sort sortieren wollen.

Als Erstes geht der Algorithmus über die Liste und wählt das kleinste Element aus. Dies findet er an vierter Stelle. Also tauscht er Platz 4 mit Platz 1. So landet die 3 am Anfang der Liste.

3 | 74 6 35 14 25

Weiter geht’s mit zweiten Durchgang. Wieder wird das kleinste Element ausgewählt. Betrachtet werden jetzt nur noch die Plätze 2 bis 6. An dritter Stelle wird der Selection Sort fündig und fügt die 6 nach der 3 ein.

3 6 | 74 35 14 25 

Als nächstes werden nur noch die übrigen Plätze 3 bis 6 betrachtet. Hierbei wählt der Algorithmus die 14 aus und tauscht entsprechend mit der 74.

3 6 14 | 35 74 25

Die Hälfte ist schon erledigt. Das kleinste Element im übrigen Teil ist die 25 auf Platz 6. Dies wird jetzt mit der 35 getauscht.

3 6 14 25 | 74 35

Die übrigen Plätze 5 und 6 werden zuletzt miteinander verglichen. Die 35 stellt sich als kleinere Zahl dar, also tauscht sie mit der 74 den Platz. Es entsteht unsere sortierte Liste und der Algorithmus ist beendet.

3 6 14 25 35 74

Wenn man den Algorithmus in der Programmierung möglichst effizient gestalten möchte, dann bietet es sich an, ein „Tauschen“ mit sich selbst zu vermeiden. Ich habe diesen Fall in dem Beispiel bewusst weggelassen, um erstmal ein grundsätzliches Verständnis für den Selection Sort zu entwickeln. Wer sich dafür interessiert, wie ein Selection Sort im Pseudocode aussieht, der kann ihn hier finden.