Selection Sort in Python
Selection Sort teilt die Liste in einen sortierten und einen unsortierten Bereich.
Was ist Selection Sort?
Selection Sort teilt die Liste in einen sortierten und einen unsortierten Bereich.
Sortiere eine Liste, indem jeweils das kleinste verbleibende Element ausgewählt wird.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Selection Sort in Python visualisieren
O(n²)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
main.py
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]))Erwartete Ausgabe
[11, 12, 22, 25, 64]So funktioniert es
In jedem Durchlauf wird das Minimum gesucht und an die nächste freie Position gesetzt. Laufzeit O(n²), zusätzlicher Speicher O(1).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.