Wir verstehen das Grundprinzip von Selection Sort: Wir suchen für jede Position (also jeden Index) einer Liste das kleinste Element der zu sortierenden Liste, entfernen es (pop) und fügend es am Ende der neuen Liste ein (append). Hier sind zwei Youtube Videos, die das Prinzip visualisieren.

Aber wie kommen wir vom Algorithmus zum Code? Wie können wir das Sortier-Rezept in Python umsetzen? Die Zutaten sind die folgenden:

• For-Schleife: for i in ...:
• Verzweigung: if <bedingung>:
• While-Schleife: while ...:
• Funktionen
• Listen

Für Selection Sort müssen wir das kleinste Element in einer Liste finden. Beginnen wir also damit.

Wie finden wir in einer Liste, zum Beispiel l = [25, 13, 38, 76], das kleinste Element?

• Wir besuchen jedes Element der Liste - dafür eignet sich eine for-Schleife.
• In einer Variable merken wir uns das bisher kleinste Element.

Python

l = [25, 13, 38, 76]
 
# Wir starten mit dem ersten Element:
minimum = l[0]
# Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
for element in l:
    if element < minimum:
        minimum = element
 
print("Kleinstes Element: {0}".format(minimum))

Im Selection Sort Algorithmus wollen wir ja Elemente vertauschen - dazu benötigen wir die Position (wir sagen: den Index) des kleinsten Elements, nicht den Wert des Elementes selber.

Statt einer direkten for-Schleife über alle Elemente schreiben wir eine indirekte Schleife, die über alle Positionen einer Liste läuft. range(len(l)) erzeugt eine Liste mit allen Positionen einer Liste von 0 bis len(l)-1. Weil wir ja mit dem ersten Element (Index 0) starten, reicht es, wenn wir erst ab dem zweiten Element (Index 1) mit dem Vergleichen beginnen, wir verwenden also range(1, len(l)), um uns einen Vergleich zu sparen.

Der Vergleich muss nun mit den [eckigen Klammern] auf die Elemente der Liste zugreifen!

Statt dem kleinsten Element merken wir uns dessen Index:

Python

l = [25, 13, 38, 76]
 
# Wir starten mit dem ersten Element:
minIndex = 0
# Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
for index in range(1, len(l)):
    if l[index] < l[minIndex]:
        minIndex = index
 
print("Index des kleinsten Elements: {0}".format(minIndex))
print("Kleinstes Element: {0}".format(l[minIndex]))

Wir können also den Index des kleinsten Elements finden - grossartig. Fürs Sortieren müssen wir das immer wieder tun; am einfachsten geht das, wenn wir unseren Code in eine Funktion verpacken, die wir aufrufen können, wenn wir sie benötigen.

Python

def find_min(l):
    # Wir starten mit dem ersten Element:
    minIndex = 0
    # Jetzt schauen wir jedes weitere Element an, und merken uns, wenn wir ein kleineres finden:
    for index in range(1, len(l)):
        if l[index] < l[minIndex]:
            minIndex = index
    return minIndex
 
l = [25, 13, 38, 76]
minIndex = find_min(l)
print("Index des kleinsten Elements: {0}".format(minIndex))
print("Kleinstes Element: {0}".format(l[minIndex]))

Wir möchten eine Funktion pop_min schreiben, die das kleinste Element aus einer Liste entfernt und zurückgibt. Mit dem Code von oben ist das nicht schwierig:

• find_min ausführen
• pop aufrufen und das Resultat zurückgeben (die Funktion pop gibt das Element zurück, das entfernt wurde).

Python

def pop_min(l):
    min_index = find_min(l)
    return l.pop(min_index)

Nun ist der Sortieralgorithmus nicht mehr schwierig: Solange die zu sortierende Liste nicht leer ist, entfernen wir jeweils das kleinste Element (pop_min) und fügen es an die Resultatliste an (append).

Python

l = [25, 13, 38, 76]
result = []
while len(l) > 0:
    next = pop_min(l)
    result.append(next)
 
print(result)

Schreibe das als Funktion selection_sort(l)!

Hier kannst du dem Algorithmus beim Sortieren zuschauen.

Falls die Liste sehr gross ist, möchten wir es vermeiden, eine neue Liste im Speicher anlegen zu müssen. Ein in-place-Algorithmus verändert die zu sortierende Liste, ohne weitere Datenstrukturen zu benötigen. Versuch dich im In-place Selection Sort!