rekursiv

Die Implementierung des MergeSort mit Hilfe der Rekursion ist recht einfach und erfordert kaum Anstrengungen, da das Mischen (kombinieren) der Teilmengen durch die oben gezeigte Funktion übernommen werden kann. Der einfachheitshalber wird hier davon ausgegangen, daß der Aufrufer ein Array als temporäre Ablage für den MergeSort zur Verfügung stellt. Dieses Buffer ist gross genug wie die zu sortierende Menge und soll im Folgenden global mit ``buffer'' angesprochen werden können. In der Praxis würde man diesen Buffer durch einen Parameter übergeben und nicht als globale Variable halten. Der ``data'' Parameter ist die Adresse des zu sortierenden Arrays, wobei sie durch ``left'' und ``right'' begrenzt wird. Das heisst die Menge wird nur in dem Raum, der durch diese Marken angegeben ist, sortiert.
Der Aufrufer der (merge_sort)-Funktion übergibt für den left-Parameter die 0 und den Index des letzten Elements in der Menge, wenn er diese gänzlich sortiert haben will.

$\begin{listing}{1} void merge_sort( int * data, int left, int right ) { if( l... ...or( i = left; i <= right; i++ ) data[i] = buffer[i - left]; } } \end{listing}$

Eine sehr elegante Lösung für das Mischen stammt von ROBERT SEDGEWICK, die er auch in seinem Algorithmenbuch (siehe Literaturliste) aufzeigt, und soll auch hier, in C implementiert, vorgestellt werden. Angemerkt sei, dass diese Implementierung des Algorithmuns nicht stabil ist, auch wenn ein Vergleich auf ``<='' erfolgt. Dies läßt sich auf einer Datenmenge wie z.B. { 16, 71, 71', 71'', 80 90 } aufzeigen und der Leser sei motiviert einen MergeSort an dieser Menge von Hand durchzuführen.

$\begin{listing}{1} sedgewick_merge_sort( int * data, int left, int right ) { ... ...r[j] ) data[k] = buffer[i++]; else data[k] = buffer[j--]; } } \end{listing}$

Hier wird das Mischen ohne Marken realisiert, indem das zweite Feld hinter das erste in umgekehrter Richtung kopiert wird. Danach sorgt eine Schleife für das Zuweisen der Elemente in die originale Datenmenge. Der Trick liegt darin, daß der Zugriff in den ``buffer'' immer kontroliert durch die Anordnung der Mengen erfolgt.

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: nicht rekursiv (iterativ) Aufwärts: Implementierung Vorherige Seite: Implementierung Inhalt

2002-05-09