Selection Sort
VergleichsbasiertFindet das Minimum im unsortierten Bereich und platziert es am Anfang — der sortierte Bereich wächst so pro Durchgang um ein Element.
Live-Visualisierung
Komplexität
| Bester Fall | O(n²) |
| Durchschnitt | O(n²) |
| Schlechtester Fall | O(n²) |
| Speicherkomplexität | O(1) |
| Stabiles Sortieren | Nein |
| In-Place | Ja |
Legende
O(1)- Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n)- Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n)- Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²)- Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil- Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place- In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert- Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert- Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.
Implementierung
TypeScript-Implementierung — direkt kopierbereit.
function selectionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
}
return arr;
}Wie es funktioniert
Selection Sort teilt das Array in einen sortierten und einen unsortierten Bereich. In jedem Durchgang durchsucht er den gesamten unsortierten Bereich nach dem Minimum und tauscht es an die erste Position des unsortierten Bereichs. Der sortierte Bereich wächst um ein Element pro Durchgang.
Besondere Eigenschaft: Selection Sort führt höchstens O(n) Tauschoperationen durch — nützlich, wenn das Verschieben von Elementen teuer ist (z. B. große Objekte im Speicher). Allerdings sind immer O(n²) Vergleiche nötig, unabhängig von der Eingabe.
Wann verwenden: Wenn die Kosten für Schreiboperationen deutlich höher sind als für Leseoperationen, und das Array klein ist. Da der Algorithmus nicht stabil ist (gleiche Elemente können ihre Reihenfolge verlieren), ist er in vielen Kontexten ungeeignet.