Overview
Wiederholtes Suchen des Minimums im unsortierten Teil und einmaliges Tauschen pro Durchlauf.
Analogy
Schüler nach Größe aufstellen: immer den Kleinsten heraussuchen und nach vorne stellen.
Step-by-step
- Für i = 0..n-2: finde Index min_idx des kleinsten Elements in arr[i..n-1].
- Tausche arr[i] mit arr[min_idx].
- Nach n-1 Durchläufen ist das Array sortiert.
Visual
[64,25,12,22,11]: 11 gefunden→tausche→[11,25,12,22,64]; 12 gefunden→[11,12,25,22,64]; ...
Common mistakes
- Pro Durchlauf wird maximal einmal getauscht – Selection Sort macht immer O(n) Tausche gesamt.
- Selection Sort ist instabil: gleiche Elemente können ihre Reihenfolge ändern.
Practice questions
- Selection Sort für absteigende Reihenfolge anpassen.
- Anzahl der Tauschoperationen mit Bubble Sort vergleichen.
Time
O(n²) Vergleiche, O(n) Tausche