Insertion Sort ist der Algorithmus, den wir meistens benützen, um Spielkarten auf die Hand zu nehmen: Die Hand ist sortiert, jede aufgenommene Karte wird an der richtigen Stelle eingefügt.

Insertion Sort in der in-place-Variante ist ähnlich wie Selection Sort: 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.

Im allgemeinen Fall ist Insertion Sort ungefähr gleich gut wie Selection Sort. Insertion Sort hat aber einen Vorteil gegenüber Selection Sort, falls die Liste bereits (weitgehend) sortiert ist: Während Selection Sort trotzdem für jedes Element den ganzen Rest der Liste absucht, um das Minimum zu bestimmen, ist das bei Insertion Sort nicht nötig.

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)):
        # 2: Fügt das Element l[position] an der richtigen Stelle <= position ein.
        insert(l, position)
 
l = [25, 13, 38, 76]
insertion_sort(l)
print(l)

Der obige Code schlägt natürlich noch fehl: NameError: name 'insert' is not defined

Erst mal schreiben wir eine leere Funktion und definieren im Kommentar, was sie tun soll:

def insert(l, index):
    """Tauscht das Element an Position 'index' solange mit seinem linken Nachbar,
       als es kleiner ist als dieser. Dann ist das Element an der richtigen Stelle eingefügt"""
    pass 

Der Code kann schon mal ausgeführt werden - nur wird natürlich noch nicht sortiert.

Wir wollen also das Element an der Position index solange mit dem linken Nachbar tauschen, als es kleiner ist als dieser. Zum Glück können wir die swap() Funktion aus Selection Sort kopieren.

def insert(l, index):
    """Tauscht das Element an Position 'index' solange mit seinem linken Nachbar,
       als es kleiner ist als dieser. Dann ist das Element an der richtigen Stelle eingefügt"""
 
    # Es gibt zwei Bedingungen, um weiter zu tauschen:
    # 1: Es hat noch Elemente links von index (index > 0)
    # 2: Das Element ist kleiner als das Element zur Linken.
    while index > 0 and l[index] < l[index - 1]:
        swap(l, index, index - 1)
        index = index - 1