Beispiel

Im folgenden sei die Datenmenge {32, 18, 22, 10, 12} betrachtet, die nun in Einzelschritten mit dem InsertionSort aufsteigend sortiert werden soll. Bevor der Algorithmus mit dem Iterieren über die Datenmenge anfägt, wird eine Marke auf das zweite Element gesetzt.

Nach diesem Durchlauf ist die 18 in der linken Menge einsortiert. Die Marke wird nach hinten gerückt und ein neuer Durchlauf gestartet.

Man beachte dass die Ausführung des Durlaufs hier abgebrochen werden kann, da sich vor der 22 nur kleinere Elemente befinden.

Dieser Durchlauf schildert einen worst case, da das Markenelement das gesammte vordere (sortierte) Feld durlaufen muss, um seine endgültige Position zu erreichen.

Und so wird die Ausführung des Algorithmus fortgesetzt bis auch das letzte Element als Markenelement abgearbeitet wurde. Man sieht wie das vordere sortierte Feld immer um ein Element anwächst und erreicht schliesslich die gesamte Grösse der ursprünglich unsortierten Menge, die letztlich sortiert vorliegt.

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 

Nächste Seite: Laufzeitkomplexität Aufwärts: Arbeitsweise Vorherige Seite: Abstrakt   Inhalt