Selection Sort kennen wir bereits. Insertion Sort ist teilweise ähnlich: wir laufen über alle Positionen der Liste: for position in range(len(l)): Alle Elemente an Positionen kleiner als position sind bereits sortiert, alle ab position noch nicht.

Insertion Sort nimmt nun das Element an position und fügt es an der richtigen Stelle der Liste vor position ein. Um das Element in-place einzufügen, gehen wir wie folgt vor: in der inneren Schleife vergleichen wir das Element l[index] jeweils mit dem nächst-vorderen Element l[index-1] und tauschen die beiden aus, wenn das vordere Element grösser ist. Dieser Vorgang wird wiederholt, bis kein Tausch mehr nötig ist, dann haben wir das Element richtig eingefügt (inserted). Weil wir nicht zum Voraus wissen, wieviele Austausch-Operationen nötig sind, bietet sich eine while-Schleife an.

Dieses Youtube Video visualisiert den Algorithmus.

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 ...:
• While-Schleife: while <bedingung>:
• Verzweigung: if <bedingung>:
• Funktionen
• Listen

Was müssen wir tun?

1. über alle Positionen (Indices) laufen: for position in range(len(l)):
2. das Element l[position] an der richtigen Position <= position einfügen.

Der zweite Teil ist noch nicht so klar, aber den ersten kennen wir von Selection Sort. Eine Möglichkeit mit dieser Situation umzugehen, ist so zu tun, als hätten wir die Lösung bereits für den zweiten Teil. Wir schreiben unfertigen Code:

def insertion_sort(l):
    # 1: An jeder Position von l:
    for position in range(len(l)):
        # Fügt das Element l[position] an der richtigen Stelle <= position ein.
        insert(l, position)
 
print(insertion_sort([25, 13, 38, 76]))