Selection Sort
Sucht in jeder Runde das Minimum des unsortierten Teils und tauscht es an dessen Anfang.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- aktiv
- Vergleich
- Tausch
- sortiert
Pseudocode
1 for i from 0 to n - 1
2 min = i
3 for j from i + 1 to n - 1
4 if a[j] < a[min]
5 min = j
6 swap a[i], a[min]
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Selection Sort teilt das Array gedanklich in einen sortierten Präfix (anfangs leer) und einen unsortierten Suffix. In jeder Runde durchläuft der Algorithmus den unsortierten Teil komplett, merkt sich den Index des kleinsten gefundenen Wertes und tauscht diesen am Ende der Runde mit dem ersten unsortierten Element. Damit wächst der sortierte Präfix um eine Position. Nach n-1 Runden ist das ganze Array sortiert. Die Anzahl der Vergleiche ist immer quadratisch (etwa n^2/2), unabhängig von der Eingabe (Best, Average und Worst Case sind alle O(n^2)). Dafür macht der Algorithmus höchstens n-1 Tauschvorgänge, was die Anzahl der Schreibzugriffe minimiert. Selection Sort arbeitet in-place (O(1) Zusatz-Speicher), ist jedoch nicht stabil: ein Tausch über eine größere Distanz kann gleichwertige Elemente über andere Werte hinweg vertauschen.
Komplexität
- Best Case
O(n^2) - Average Case
O(n^2) - Worst Case
O(n^2) - Zusatz-Speicher
O(1)
Wann verwenden?
Sinnvoll, wenn Schreibzugriffe teuer sind, etwa auf Flash-Speicher mit begrenzten Write-Zyklen. Selection Sort macht höchstens n - 1 echte Tauschvorgänge, während Bubble oder Insertion Sort deutlich häufiger ins Array schreiben.