Interaktive Demo
Selectionsort-Visualisierung
Selectionsort sucht das kleinste der übrigen Elemente und tauscht es nach vorne, eine Position nach der anderen. Er braucht wenige Schreibzugriffe, aber immer O(n²) Vergleiche.
Egal welche Ausgangsreihenfolge: Selectionsort braucht für 11 Elemente immer dieselben 55 Vergleiche. Mit „Wenige verschiedene Werte“ zeigt sich, dass er nicht stabil ist.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Unsortiertes Element
- Bisher kleinstes
- Verglichenes Element
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n²)
Auch ein sortiertes Array wird für jedes nächste Minimum komplett durchsucht.
Mittlerer Fall
O(n²)
Immer n(n − 1)/2 Vergleiche, unabhängig von der Eingabe.
Schlechtester Fall
O(n²)
Dieselben n(n − 1)/2 Vergleiche, aber nie mehr als n − 1 Vertauschungen.
Zusätzlicher Speicher
O(1)
Nur die Position des aktuellen Minimums wird gemerkt.
Stabil
Nein
Das Tauschen des Minimums nach vorne kann ein gleiches Element überspringen.
In-place
Ja
Elemente werden nur innerhalb des Arrays getauscht.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort diese Seite | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Minimum suchen
Vom Anfang des unsortierten Teils an wird jedes übrige Element mit dem bisher kleinsten verglichen.
2. Nach vorne tauschen
Das kleinste Element wird an den Anfang des unsortierten Teils getauscht. Dort steht es an seiner endgültigen Position, und der unsortierte Teil schrumpft um eins.
3. Wenig schreiben, viel vergleichen
Selectionsort braucht nie mehr als n − 1 Vertauschungen, das hilft, wenn Schreiben teuer ist. Er kann aber nicht früher aufhören: Selbst ein sortiertes Array kostet n(n − 1)/2 Vergleiche.