Auswahlsortierung (englisch: Selection Sort) arbeitet nach einem intuitiven Prinzip: Suche das kleinste Element in der Liste und stelle es an den Anfang. Dann suche das kleinste Element im Rest und stelle es an die zweite Stelle — und so weiter.
So funktioniert Auswahlsortierung
Stell dir vor, du sortierst eine Reihe von Karten mit den Zahlen [64, 25, 12, 22, 11]:
- Suche das Minimum im gesamten Bereich →
11(Position 4) - Tausche
11mit dem ersten Element →[11, 25, 12, 22, 64] - Suche das Minimum im Rest (ab Position 1) →
12(Position 2) - Tausche
12mit dem zweiten Element →[11, 12, 25, 22, 64] - Fortfahren...
Schritt-für-Schritt-Übersicht:
| Durchlauf | Liste nach dem Tausch | Sortierter Teil |
|---|---|---|
| 0 | [11, 25, 12, 22, 64] | 1 Element |
| 1 | [11, 12, 25, 22, 64] | 2 Elemente |
| 2 | [11, 12, 22, 25, 64] | 3 Elemente |
| 3 | [11, 12, 22, 25, 64] | 4 Elemente |
| Fertig | [11, 12, 22, 25, 64] | 5 Elemente |
Python-Implementierung
def auswahl_sortierung(elemente):
n = len(elemente)
for i in range(n - 1):
# Index des Minimums im unsortierten Teil finden
min_index = i
for j in range(i + 1, n):
if elemente[j] < elemente[min_index]:
min_index = j # neues Minimum gefunden
# Minimum an den Anfang des unsortierten Teils tauschen
if min_index != i:
elemente[i], elemente[min_index] = elemente[min_index], elemente[i]
return elemente
zahlen = [64, 25, 12, 22, 11]
print(auswahl_sortierung(zahlen)) # [11, 12, 22, 25, 64]
Auswahlsortierung führt immer genau n - 1 Tauschoperationen durch — eine pro Durchlauf. Das ist ein Vorteil, wenn Tauschoperationen teuer sind. Bubble-Sort kann dagegen viele unnötige Tauschvorgänge durchführen.
Vergleich mit Bubble-Sort
| Eigenschaft | Bubble-Sort | Auswahlsortierung |
|---|---|---|
| Tauschoperationen | Viele (bis n²/2) | Wenige (genau n-1) |
| Vergleiche | ~n²/2 | ~n²/2 |
| Zeitkomplexität | O(n²) | O(n²) |
| Stabil? | Ja | Nein |
| Einfachheit | Sehr einfach | Einfach |
Ein Sortieralgorithmus gilt als stabil, wenn er gleiche Elemente in ihrer ursprünglichen Reihenfolge belässt. Bubble-Sort ist stabil (tauscht nur, wenn eines größer ist), Auswahlsortierung nicht unbedingt (kann gleiche Elemente umordnen).
Wann eignet sich Auswahlsortierung?
Auswahlsortierung ist nützlich, wenn:
- Die Liste klein ist (weniger als ~50 Elemente)
- Tauschoperationen besonders aufwändig sind
- Einfachheit wichtiger ist als Geschwindigkeit
Wie Bubble-Sort hat Auswahlsortierung eine Zeitkomplexität von O(n²) und ist daher für große Datenmengen ungeeignet. In der Praxis nutzt man effizientere Algorithmen wie Mergesort oder Quicksort.
Übungsaufgaben
Wie sieht die Liste [29, 10, 14, 37, 13] nach dem zweiten Durchlauf der Auswahlsortierung aus?
Antwort anzeigen
Warum macht Auswahlsortierung immer genau n-1 Tauschoperationen, unabhängig von der Ausgangsreihenfolge?