Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Kapitel II:

Zyklisches Verschieben von sortierten Teilfolgen

Bei Swap-Sort mit zyklischen Verschieben wurde bei der Betrachtung von sortierten Teilfolgen erwähnt, daß man um sortierte Teilfolgen zu verschieben nur 2 lineare Felder benötigt. Dies und eine praktikable Verbesserung, um dem Aufwand beim binären Suchen zu reduzieren, werden wir hier betrachten.

Doch vorher betrachten wir noch, was passiert, wenn wir Blöcke in einem Speicherbereich verschieben.
 

Block 1

Block 2

Block 3

 Block 4

Block 5

Block 2

Block 4

Block 1

Block 5

Block 3


Nun verschiebt man jedes einzelne Element der Blöcke der 1. Zeile mittels zyklischen Verschieben, so daß man sie in die 2. Zeile überführen kann.





Nun sieht man ganz klar, daß das Verschieben von Speicherbereichen einfacher durch zyklisches Verschieben gelöst werden kann, indem man alle Zyklen, die wir vorfinden 1 mal durchlaufen.

Man kann diese Zyklen abarbeiten ohne daß man ein zusätzliches Bitfeld benötigt, indem man die Zyklen immer in einer fest vorgegebenen Reihenfolge z.B. von links nach rechts abarbeitet und bevor man eine Verschiebung des Speicherbereiches durchführt – außer es ist der 1. Zyklus – einen Zyklustest durchführt. D.h. man macht einen Leerlauf ohne irgend etwas zu verschieben und kommt der Zyklus zur Position des Startelementes zurück ohne daß er auf eine Position vor dem Startelement stößt, so weiß man, daß dieser Zyklus noch nicht abgearbeitet wurde, andernfalls wurde er abgearbeitet. Somit benötigt man kein zusätzliches Bitfeld.

Wenn man aber zyklisches Verschieben bei sortierten Teilfolgen anwendet, stoßen wir auf das Problem, daß wenn wir denn Index der sortierten Teilfolge berechnen wollen, die ein Element enthält, das an eine bestimmte Position verschoben werden soll, diesen Index am besten durch ein Suchverfahren, welche eine Verschiebungsliste durchsucht, berechnen. Diese Berechnung kann zeitaufwendig sein, wenn man viele Teilfolgen zu verschieben hat. Daher ist es angebracht, falls es leicht durchführbar ist, schon bearbeitete Teilfolgen, sobald wie möglich aus der Verschiebungsliste zu entfernen. Arbeiten wir die Zyklen wie im oben angegeben von links nach rechts ab, so können wir Teilfolgen, die bereits abgearbeitet wurden und auf der linken Seite des Startelementes des gerade abzuarbeitenden Zyklus stehen, entfernen. Genausogut kann man am anderen Ende der Verschiebungsliste ebenfalls Teilfolgen entfernen. Allerdings muß man dies speziell behandeln und man benötigt in diesem Fall ein Bitfeld, welches schon verschobene Elemente markiert. Durch die Markierungen erkennt man bereits verschobenen Elemente. Stehen diese Markierungen für das Ende der Verschiebungsliste, entfernt man die Teilfolgen. Man kann dieses Bitfeld aber durch eine spezielle Behandlung so ausrichten das eine gewisse Position stets mit einem noch nicht verschobenen Element übereinstimmt. Diese Bitfelder kann man wiederum selbst bei einem Zyklustest mitverwenden. Aus diesem Grund kann man auch am Anfang der Verschiebungsliste ebenfalls ein Bitfeld verwenden, um die Anzahl der Zyklustests zu verringern.

Beim Swap-Sort-Verfahren lassen sich sogar an 4 Stellen Teilfolgen, falls sie abgearbeitet wurden, aus der Verschiebungsliste auf einfache Weise entfernen.

Rest von Teil 1

Rest von Teil 3

Aussortierte Elemente von Teil 1 und Teil 3

Aussortierte Elemente von Teil 2 und Teil 4

Rest von Teil 2

Rest von Teil 4

D.i. beim Anfang und Ende aussortierten Elemente von Teil 1 und Teil 3 sowie am Anfang und am Ende der aussortierten Elemente von Teil 2 und Teil 4.
 

zurück zur Inhaltseite von Swap-Sort, dem effizienten Sortier-Algorithmus