Wir verstehen das Grundprinzip von Selection Sort: Wir suchen für jede Position (also jeden Index) einer Liste das kleinste Element der restlichen Liste, dann tauschen wir es an die momentane Position. 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>:
• 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 l 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]))

In der In-place-Variante haben wir nur eine einzige Liste. Die Elemente vor position sind sortiert, die nachher unsortiert. Das nächste Minimum suchen wir also nicht in der ganzen Liste (also ab dem Index 0), sondern ab einem bestimmten Index. Wir fügen dafür der Funktion einen Parameter start hinzu, ab dem nach dem Minimum gesucht wird:

Python

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

Für alle in-place Sortier-Algorithmen benötigen wir die Fähigkeit, zwei Elemente an den Positionen i und j zu vertauschen. Am einfachsten schreiben wir eine Hilfsfunktion, die das für uns erledigt. Die Funktion benötigt als Parameter die Liste und die zwei Positionen.

Python

def swap(l, i, j):
    # Element an Position i zwischenspeichern, weil wir es nachher überschreiben:
    temp = l[i]
    l[i] = l[j]
    l[j] = temp

Hinweis

def swap(l, i, j):
    l[i], l[j] = l[j], l[i]

Nun ist der Sortieralgorithmus nicht mehr schwierig. Wir benötigen eine Schleife, die über alle Positionen der Liste läuft. An jeder Position position suchen wir das kleinste Element ab der Position. Wir vertauschen das kleinste Element mit dem Element an position.

Python

l = [25, 13, 38, 76]
 
for position in range(len(l)):
    minIndex = find_min(l, position)
    swap(l, position, minIndex)
 
print(l)

Schreibe das als Funktion selection_sort(l)!

Hier kannst du dem Algorithmus beim Sortieren zuschauen.