Selectionsort (selection sort) in Python
In dieser Lektion implementierst du Selectionsort, indem du immer wieder das kleinste Element suchst und an die richtige Stelle setzt.
Einführung
Das Problem
Manche Sortieralgorithmen versuchen, Elemente möglichst selten zu verschieben. Das zählt, wenn das Verschieben eines Elements teuer ist. Selection Sort zeigt eine andere Strategie als Bubble Sort: erst das richtige Element finden und es dann genau einmal verschieben.
Stell es dir so vor
Selection Sort ist, als würdest du ein Team der Größe nach aufstellen. Du schaust dir alle an, die noch warten, rufst die kleinste Person auf und stellst sie an den nächsten Platz in der Reihe. Dann suchst du unter den übrigen wieder die nächstkleinste, bis niemand mehr übrig ist.
for start in range(len(result)):📍 Der nächste freie Platz in der Reiheminimum = start🤔 Annehmen, dass diese Person die kleinste istresult[index] < result[minimum]🔎 Den Rest nach jemand Kleinerem absuchenresult[start], result[minimum] = ...🔄 Die kleinste Person auf den freien Platz stellenSelection Sort sucht wiederholt das kleinste Element im unsortierten Teil der Liste und tauscht es an die nächste Position des sortierten Teils. Er braucht O(n²) Vergleiche, aber höchstens n - 1 Tauschvorgänge.
Das Wichtigste
- Alles links von
startist schon sortiert, alles abstartnoch nicht. minimummerkt sich den Index des kleinsten Werts, der bisher im unsortierten Teil gefunden wurde.- Die innere Schleife
for index in range(start + 1, len(result)):durchsucht den Rest der Liste. result[start], result[minimum] = result[minimum], result[start]tauscht genau einmal pro Position.
Wann verwendet man das?
- Sortierstrategien lernen und vergleichen.
- Situationen, in denen Schreiben oder Verschieben teuer und Vergleichen billig ist.
- Die k kleinsten Elemente finden, indem du nach k Durchgängen aufhörst.
Wann du es nicht brauchst
- Echte Programme:
sorted()ist viel schneller. - Fast sortierte Daten: Selection Sort durchsucht trotzdem alles, während Insertion Sort schnell fertig ist.
Selectionsort (selection sort) in Python visualisieren
O(n²)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Ergebnis der Ausführung
[11, 12, 22, 25, 64]
Erklärung des Codes
Die Variable minimum merkt sich die Position des kleinsten Werts im Rest der Liste. Am Ende jedes Durchlaufs wird dieser Wert an die Position start getauscht. Wegen der vielen Vergleiche hat der Algorithmus immer die Komplexität O(n²), er vertauscht aber höchstens n-mal.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
In der inneren Schleife tauschen
Dann wird daraus ein langsameres, unübersichtliches Verfahren mit vielen Tauschvorgängen.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Array Minimum Finde den kleinsten Wert in einer Liste. Einfach
- K-th Smallest Element Find the k-th smallest value without fully sorting. Mittel