Abstrakt

Wie schon gesagt ist das Prinzip des Insertion Sorts einfach. Im folgenden sind die einzelnen Schritte des Algorithmus bei seiner Vorgehensweise niedergeschrieben.
Zu Begin des Ablaufs wird eine Marke auf das zweite Element der Datenmenge gelegt. Diese Marke trennt das sortierte Feld vom Unsortierten. Nun wird für das Element an der Marke die richtige Position in der Sortierten Menge heraus gefunden und dort eingefügt. Dazu wird die sortierte Menge von hinten so weit durchlaufen bis das Markenelement seine Position erreicht; bereits beim Durchlaufen wird das Element mit vorgeschoben. Nach einem Durlauf wird die Marke um ein Element nach hinten (zum Mengenende hin) gerückt und ein neuen Durchlauf mit dem neuen Markenelement ausgeführt. Dieses Vorgehen wird so lange wiederholt, bis auch das letzte Element in der Menge abgearbeitet wurde.

  1. Falls die Marke nicht über das letzte Element hinaus positioniert ist, wird mit dem nächsten Punkt verfahren, ansonsten terminiert der Algorithmus.
  2. Nun wird das Markenelement so weit vorgeschoben, bis es seine richtige Position erreicht hat, sprich bis hinter ein kleineres Element in dem bereits sortierten (vorderderen) Feld der Datenmenge positioniert.
  3. Die Marke wird um eine Stelle zum Datenende hin verschoben.
  4. Die Ausführung setzt sich beim ersten Punkt wieder fort.

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Beispiel Aufwärts: Arbeitsweise Vorherige Seite: Arbeitsweise   Inhalt

2002-05-09