Python-Algorithmen

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.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Vom Team-Aufstellen zum Code
for start in range(len(result)):📍 Der nächste freie Platz in der Reihe
minimum = start🤔 Annehmen, dass diese Person die kleinste ist
result[index] < result[minimum]🔎 Den Rest nach jemand Kleinerem absuchen
result[start], result[minimum] = ...🔄 Die kleinste Person auf den freien Platz stellen
Ein Tausch pro Position, nachdem der ganze unsortierte Teil durchsucht wurde.
In einem Satz

Selection 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

  1. Alles links von start ist schon sortiert, alles ab start noch nicht.
  2. minimum merkt sich den Index des kleinsten Werts, der bisher im unsortierten Teil gefunden wurde.
  3. Die innere Schleife for index in range(start + 1, len(result)): durchsucht den Rest der Liste.
  4. 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

Code ausführen →
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]))
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

In der inneren Schleife tauschen

Dann wird daraus ein langsameres, unübersichtliches Verfahren mit vielen Tauschvorgängen.

Problem
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Lösung
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.

Alle Challenges