Insertion-Sort

Sorts werden verwendet, um unsortierter Objekte in eine richtige Reihenfolge zu bringen. Es gibt drei Sortierverfahren, die sich in ihrer Sortiermethode unterscheiden, unter anderem den InsertionSort, den BubbleSort und den SelectionSort.

Allgemein

Bei der Insertionsort Sortierung werden zwei Stapel gebildet, ein sortierter und ein unsortierter Stapel. Bei der Bewegung der Objekte von der unsortierter in den sortierten Stapel werden die Zahlen immer analysiert und in der richtige Reihenfolge gebracht. Außerdem braucht man einen Zwischenspeicher, der die zu bewegende Zahl speichert.

Beispiel

Stellt man sich ein Kartenspiel vor, wobei am Anfang die Karten des Blatts verdeckt auf dem Tisch liegen, so gilt: Die Karten werden nacheinander aufgedeckt und an der korrekten Position in das Blatt, das in der Hand gehalten wird, eingefügt. Um die Einfügestelle für eine neue Karte zu finden, wird diese sukzessive (von links nach rechts) mit den bereits einsortierten Karten des Blattes verglichen. Zu jedem Zeitpunkt sind die Karten demnach in der Hand sortiert und bestehen aus den zuerst vom Tisch entnommenen Karten.

Struktogramm zum Insertion-Sort