Mischen

Das Mischen (eng. ``merge'') von zwei Mengen ist letzlich das Kernproblem des MergeSorts, weswegen nun allein das Mischen von zwei bereits sortierten Mengen A und B beläuchtet werden soll. Die Menge A soll aus N und die Menge B aus M Elementen bestehen. Der einfachheitshalber soll eine dritte Menge C mit Platz für N+M Elemente zur Verfügung stehen, in welcher die Elemente aus A und B sortiert abgelegt werden sollen.

In der Programmiersprache C, könnte man dieses Problem durch die folgende Funktion bewaeltigen, wobei die Mengen durch Arrays realisiert sind. Die Namen der Parameter der Funktion nehmen Bezug auf die Erläuterungen im vorherigen Abschnitt.

$\begin{listing}{1} void merge( int * a, int N, int * b, int M, int * c, int... ...f( i < N ) c[k] = a[i++]; else if( j < M ) c[k] = b[j++]; } } \end{listing}$

Die Überprüfung der Variablen i und j auf ihre Güligkeit ``0 <= i < N && 0 <= j < M'' ist notwendig, um den Zugriff auf die Mengen A und B sicher zu stellen.

Eine andere Möglichkeit den Zugriff sicher zu stellen wäre, den Mengen A und B jeweils ein Markenelement anzufügen, das grösser ist, als alle anderen Elemente in den Mengen.
Somit könnten die Abfragen von i und j auf ihre Gültigkeit weggelassen werden, denn falls ``a[i] < b[j]'' nicht zutrifft, wobei i das Markenelement in der Menge A anspricht, wird auf die Menge B zugegriffen. Man könnte meinen, daß sich ein Fehler in dieser Methode beim Zugriff auf die Menge B versteckt, doch dem ist nicht so. Falls i und j die Mengen A und B abgearbeitet haben, so ist k inzwischen auf NM angewachsen und die Schleife wird abgebrochen. Der Nachteil dieser Methode ist, daß die Markenelemente den Menge angefügt werden müssen. Was sich zunächst einfach anhöhrt, gestaltet sich bei der Implementierung mit einigen Problemen behaftet. Hier einige der kritischen Stellen:

Die Mengen müssen gross genug sein, um jeweils das zusätzliche Element aufnehmen zu können. Sind die Mengen im dynamischen Speicher, kann man diese zur Laufzeit demensprechend um ein Element vergrössern.
In Mengen, welche durch ``verkettete Listen'' implementiert sind, kann zwar mit Leichtigkeit ein Element angefügt werden, dafür muss jedoch das Ende der Menge durch eine Iteration gefunden werden, was eine Laufzeit von kostet, wobei n die Anzahl der Elemente in der jeweiligen Menge ist.
Die zusätzlich angefügten Elemente müssen wieder enfernt werden.

Wenn man davon ausgeht, daß die beiden Mengen A und B Arrays sind, die aus N+1 bzw. M+1 Plätzen für Elemente bestehen und deren N bzw. M Pläze mit Elementen initializiert sind, könnte man die obige Funktion wie folgt vereinfachen:

$\begin{listing}{1} void merge_vereinfacht( int * a, int N, int * b, int M, ... ...k++ ) if( a[i] <= b[j] ) c[k] = a[i++]; else c[k] = b[j++]; } \end{listing}$

Wüschenswert wäre bei beiden vorgestellten Funktionen, wenn die Datenmengen A und B in einer Menge C representiert waeren, und auch wieder in dieser Menge abgelegt werden würden. Die beiden Menge A und B würden dann z.B. in einem Array nacheinander liegen und durch Indizes ansprechbar sein.

Diese Problemstellung ist zwar nicht ganz einfach, aber realisierbar. Sie wird später im Zusammenhang mit dem ``in-place'' MergeSort erleutert. Tatsächlich ist dies das Problem, mit dem sich die ``in-place'' Variante des Algorithmus befasst und es von der anderen unterscheidet.

Nächste Seite Aufwärts Vorherige Seite Inhalt

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

2002-05-09