Sortieren durch Einfügen / Insertionsort

Eine Volkstanz-Sortieranimation

Auf YouTube gibt es ein interessantes Video zum Sortieren durch Einfügen: Insertionsort mit Volkstanz.

Aufgabe 1

Schaue dir das Video genau an. Wie gehen die Tänzer beim Sortieren vor? Kannst du die Grundidee des benutzten Sortierverfahrens beschreiben?

Die Grundidee

Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Einfügen" oder "Insertionsort" genannt wird.

Aufgabe 2

(a) Erkläre die Bezeichnung "Sortieren durch Einfügen": Was wird hier wo und wie eingefügt?

(b) Führe das Sortierverfahren Sortieren durch Einfügen am folgenden Beispiel weiter durch. Dokumentiere alle Schritte.

[25]     [17  32  56  25  19   8  66  29   6  20  29]
           ^

[17  25]     [32  56  25  19   8  66  29   6  20  29]
               ^

[17  25  32]     [56  25  19   8  66  29   6  20  29]
                   ^

[17  25  32  56]     [25  19   8  66  29   6  20  29]
                       ^

[17  25  25  32  56]     [19   8  66  29   6  20  29]
                           ^
...

Ablaufmodellierung

Der Sortierablauf soll jetzt präzisiert werden.

[25]     [17  32  56  25  19   8  66  29   6  20  29]
           ^

[17  25]     [32  56  25  19   8  66  29   6  20  29]
               ^

[17  25  32]     [56  25  19   8  66  29   6  20  29]
                   ^

[17  25  32  56]     [25  19   8  66  29   6  20  29]
                       ^

[17  25  25  32  56]     [19   8  66  29   6  20  29]
                           ^
...

Beachte, dass beim Sortiervorgang eine neue Liste angelegt werden kann (siehe oben), oder dass der gesamte Sortiervorgang innerhalb der Ausgangsliste erfolgen kann (siehe unten).

[25| 17  32  56  25  19   8  66  29   6  20  29]
      ^

[17  25| 32  56  25  19   8  66  29   6  20  29]
          ^

[17  25  32| 56  25  19   8  66  29   6  20  29]
              ^

[17  25  32  56| 25  19   8  66  29   6  20  29]
                  ^

[17  25  25  32  56| 19   8  66  29   6  20  29]
                      ^
...

Informell lässt sich dieser Sortierablauf so beschreiben:

ALGORITHMUS insertionsort
Übergabe: Liste
sortierter Bereich besteht aus dem ersten Element der Liste 
unsortierter Bereich ist die Restliste (ohne das erste Element)
SOLANGE der unsortierte Bereich Elemente hat:
    entferne das erste Element aus dem unsortierten Bereich
    füge es an der richtigen Stelle im sortierten Bereich ein
Rückgabe: sortierter Bereich

Aufgabe 3

Entwickle ein Struktogramm zur Präzisierung des Ablaufs.

Aufgabe 4

Implementiere den Algorithmus insertionsort und teste das Sortierverfahren.