Sortieren durch Einfügen / Insertionsort
Die Grundidee
Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Einfügen" oder "Insertionsort" genannt wird.
Aufgabe 1
(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 2
Entwickle ein Struktogramm zur Präzisierung des Ablaufs.
Aufgabe 3
Implementiere den Algorithmus insertionsort und teste das Sortierverfahren.
