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