i

Sortieren durch Einfügen / Insertionsort

Die Grundidee

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

Insertionsort

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.

Suche

v
2.4.1.1.2
inf-schule.de/algorithmen/komplexitaet/sortieren/sortieralgorithmen/insertionsort
inf-schule.de/2.4.1.1.2

Rückmeldung geben