Biderektionaler BubbleSort

Wie bereits erwähnt gibt es eine verbesserte Variente des einfachen BubbleSorts, die allerdings Hand in Hand mit dem ``Vorzeigigen Abbrechen'' arbeitet und so eine Optimierung herauskristalisiert. Die Idee hinter dem ``bidirektionalen'' BubbleSort ist, dass von beiden Seiten während dem Ablauf sortierte Felder in der zu sortierenden Datenmenge aufgebaut werden. Eine Abfrage, ob die Menge bereits sortiert ist, sorgt dafür, dass der Algorithmus vorzeitig terminieren kann. Da sich von beiden Seiten eine sortierte Menge aufbaut, ist die Chance, früher terminieren zu können, grösser als beim einfachen BubbleSort.

Der wesentliche Unterschied zwischen den beiden Arten des Algorithmus besteht darin, die Durchläufe in unterschiedlichen Richtungen zu steuern. Während der einfache BubbleSort die Datenmenge immer in einer Richtung (von vorn nach hinten) durchläuft, welchselt die biderektionale Variante die Richtung. Einmal durchäuft sie die Datenmenge von vorn nach hinten, beim nächsten mal von hinten nach vorn.

Bei dieser Variente muss allerdings mit zwei Marken gearbeitet werden, was sich allerdings nicht als ein Problem erweisen sollte. Die zwei Marken werden jeweils auf das letzte und erste Element der Menge gesetzt, danach die Durchläufe gestartet. Jeder Durchlauf startet allerdings bei der ersten Marke und endet bei der Zweiten bzw. umgekehrt. Der Algorithmus terminiert genau dann, wenn die zwei Marken sich ``treffen'' oder kein Element im letzten Durchlauf vertauscht wurde. Wie bereits gesagt wird die Richtung des Durchlaufs immer abgewechselt. Somit erreicht es die Implementierung, beim Durchlauf von vorn nach hinten, das grösste Element, und beim Durchlauf von hinten nach vorn, das kleinste Element in der Datenmenge auf die richtige Position zu plazieren. Nach einigen Schritten kristalliesieren sich in der zu sortierenden Datemenge zwei sortierte Felder von beiden Enden der Menge.

Angemerkt sei hier, dass sich die Funktionsweise des Algorithmus in seiner Struktur nicht ändert. Es werden wie beim einfachen BubbleSort die Elemente auf die gleich Art und Weise verglichen und vertauscht. Lediglich die Durchläufe sind anders organisiert.

Für eine Implemntierung in C sei eine Funktion ``swap'' definiert, welche die Addressen von zwei Variablen erhaelt und die Inhalte der Variablen vertauscht. Diese Funktion dient nur zur Hilfe um spaeter vom Sortieralgorithmus aufgerufen zu werden.

$\begin{listing}{1} void swap( int * a, int * b ) { int tmp; tmp = *a; *a = *b; *b = tmp; } \end{listing}$

Nun die Implementierung des bidirektionalen BubbleSorts. Die zwei Marken werden durch die Variablen left und right dem entsprechend benannt. Die äusserste while Schleife kontroliert die Durchläufe, wohingegen die inneren for Schleifen die Durchläufe selbst darstellen. Einmal von left nach right, dann umgekehrt. Die swapped Variable wird dazu genutzt um festzustellen, ob Datenelemente beim letzten Durchlauf vertausch wurden; falls nicht ist die Menge sortiert, die Ausfühurng springt aus der Hauptschleife heraus und die Funktion kehrt zu Aufrufer zurück. Die Parameter der folgenden Funktion sind die Adresse des Speicherkontiniums, sowie die Anzahl der Elemente in der Datenmenge data.
Zu Beachten ist das sich die Durchläufe immer zwischen den Marken left und right bewegen und somit weniger Elemente abarbeiten als der einfache BubbleSort.

$\begin{listing}{1} ...$

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Vergleich Aufwärts: Optimierungen Vorherige Seite: Vorzeitiges Terminieren Inhalt

2002-05-09