Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort/Oberon

MergeSort in Oberon

In Oberon sieht der MergeSortieralgorithmus wie folgt aus:

 1. PROCEDURE MergeSort* ( VAR a : ARRAY OF LONGINT ; n : LONGINT );
 2.     VAR
 3.         i : LONGINT;
 4.         b : POINTER TO ARRAY OF LONGINT;

 5.     PROCEDURE MergeSortRek ( VAR a, b : ARRAY OF LONGINT ; von, bis : LONGINT );
 6.         VAR
 7.             i, j, k, m, temp : LONGINT;
 8.         BEGIN

                (* Ein Element ist immer sortiert... *)
 9.             IF bis = von THEN
10.                 RETURN;

                (* Zwei Elemente koennen trivial sortiert werden... *)
11.             ELSIF bis - von = 1 THEN
12.                 IF a[bis] < a[von] THEN
13.                     b[bis] := a[von]; b[von] := a[bis];
14.                 ELSE
15.                     RETURN;
16.                 END

                (* Bei mehreren Elementen... *)
17.             ELSIF bis - von > 1 THEN

                    (* Divide and conquer *)
18.                 m := von + (bis - von) DIV 2;
19.                 MergeSortRek(b,a,von,m); MergeSortRek(b,a,m+1,bis);

                    (* Durchlaufe die zwei Haelften und fuelle die Werte in b *)
20.                 i := von; j := m+1; k := von;
21.                 WHILE (i <= m) & (j <= bis) DO
22.                     IF a[i] < a[j] THEN
23.                         b[k] := a[i]; INC(i);
24.                     ELSE
25.                         b[k] := a[j]; INC(j);
26.                     END;
27.                     INC(k);
28.                 END;
29.                 WHILE i <= m DO b[k] := a[i]; INC(k); INC(i); END;
30.                 WHILE j <= bis DO b[k] := a[j]; INC(k); INC(j); END;

31.             END
32.         END MergeSortRek;

33.     BEGIN

            (* Ueberpruefen der Arraylaenge *)
34.         IF n > LEN(a) THEN
35.             Out.String("Fehler: n groesser als Arraylaenge!"); Out.Ln;
36.         END;

            (* Temporaerarray b erzeugen, a hineinkopieren *)
37.         NEW(b,n);
38.         FOR i := 0 TO n-1 DO b[i] := a[i] END;

            (* Rekursion starten *)
39.         MergeSortRek(b^,a,0,n-1);

40.     END MergeSort;

Die eigentliche Prozedur fängt bei Zeile 33 an. Dort wird das temporäre Array b erzeugt und mit den Werten von a gefüllt. Warum wir es mit den Daten von a füllen, obwoh es nur als temporärer Speicher gedacht ist, werden wir noch sehen. Die Prozedur ruft dann in Zeile 39 die rekursive Unterprozedur MergeSortRek.

Die Unterprozedur MergeSortRek sortiert die Elemente von von nach bis und legt sie im Array b ab. Da die Daten in beiden Arrays a und b vorhanden sind ist es egal, aus welchem Array sie gelesen werden.

Die Unterprozedur unterscheidet zwischen drei Faellen:

• Der Bereich von von bis bis umfasst genau ein Element (Zeile 9). Dieses Element ist schon sortiert und sowohl in a als in b vorhanden. Die Unterprozedur muss nichts machen.
• Der Bereich von von bis bis umfasst genau zwei Elemente (Zeile 11). Die Reihenfolge der Elemente wird ueberprueft (Zeile 12) und gegebenfalls vertauscht (Zeile 13). Sind beide Elemente schon in der richtigen Reihenfolge, muess nichts gemacht werden (Zeile 15).
• Beinhaltet der Bereich von von bis bis mehr als zwei Elemente, wird er zuerst aufgeteilt (Zeile 18) und beide Haelften werden sortiert (Zeile 19). Die Berechnung von m wird nicht einfach als (von + bis) DIV 2 berechnet, da wenn von und bis sehr gross sind deren Summe zu einem Ueberlauf fuehren kann. Wir beachten auch, dass wir beim rekursiven Aufruf von MergeSortRek die Arrays a und b vertauscht haben. Somit liegt das sortierte Resultat in a. In den Zeilen 20 bis 28 durchlaufen wir dann beide Unterarrays solange in beiden mindestens ein Element vorhanden ist und fuellen das Array b mit den sortierten werten auf. Ist eines der Teilarrays erschoepft, so wird der Rest des anderen direkt nach b kopiert (Zeilen 29 und 30).

Wichtig bei dieser Implementation ist, dass wir immer die Arrays a und b bei der Aufruf der Rekursion vertauschen, damit die sortierten Elemente am Schluss im richtigen Array sitzen.