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:

• 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: " + minimum)

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

Statt eine for-Schleife über alle Elemente schreiben wir eine 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.

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: " + minIndex)
print("Kleinstes Element: " + l[minIndex])

Wir können also den Index des kleinsten Elements finden - grossartig. Für die Suche 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: " + minIndex)
print("Kleinstes Element: " + l[minIndex])

Zudem möchten wir kontrollieren, ab welcher Position nach dem Minimum gesucht wird, und geben diese Information als zusätzliches Argument an die Funktion mit:

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, 0)
print("Index des kleinsten Elements: " + minIndex)
print("Kleinstes Element: " + l[minIndex])