====== Mergesort ======
===== Vorbemerkungen =====
Mergesort und Quicksort sind essentielle Bestandteile der heutigen informationstechnologischen Infrastruktur - ohne diese beiden Algorithmen sähe die Welt anders aus, da praktisch alle IT Systeme ständig Daten sortieren müssen.
* Mergesort kommt beispielsweise zum Einsatz bei Java-Methoden zum Sortieren von Objekte, sortieren in Perl, stabile Sortierverfahren bei CPP und Python, JavaScript Implementation von Firefox. Mergesort war einer der ersten in den 1940er Jahren auf dem {{wp>EDVAC}} ausgeführten Algorithmen.
* Quicksort ist die Basis beim Sortieren von primitiven Typen in Java, qsort bei C, Visual C, Python, Matlab und JavaScript in Chrome basierten Browsern.
===== Grundsätzliche Funktionsweise =====
Mergesort ist eine Divide-and-Conquer Algorithmus, der prinzipiell folgendermaßen funktioniert:
* **Teile** das Array in zwei Hälften (Divide).
* Sortiere (**rekursiv**) die beiden Hälften (Sort).
* **Füge** die beiden Hälften wieder zu einem sortierten Array **zusammen** (Merge / Conquer).
{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:mergesort.drawio.png |}}
===== Zentrale Teilaufgabe: Merge =====
Das Zusammenfügen der sortierten Teilarrays ist ein zentraler Bestandteil des Mergesort-Verfahrens, darum schauen wir uns das hier an einem Beispiel nochmal etwas genauer an, wie man diesen Vorgang verstehen und implementieren kann.
Gegeben sind also zwei sortierte Teilarrays, die zu einem sortierten Array zusammengefügt werden sollen:
{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:merge.drawio.png |}}
Dazu gehen wir wie folgt vor:
* Zunächst kopieren wir das gesamte Array in ein "Speicherarray".
* Anschließend verwenden wir drei Indizes:
* i: Beginnt beim ersten Element des ersten Teilarray des Speicherarrays
* j: Beginnt beim ersten Element des zweiten Teilarrays im Speicherarray
* k: Beginnt beim ersten Element des Arrays, das zusammengesetzt werden soll
{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:merge2.drawio.png |}}
i und j laufen jetzt durch die Teilarrays, die zugehörigen Elemente werden verglichen. Das kleinere der beiden Elemente wird ins ursprüngliche Array übernommen und der jeweilige Index inkrementiert. Gelangt ein Index ans Ende, kann der Rest des unvollständig abgearbeiteten Teilarrays übernommen werden.
----
{{:aufgabe.png?nolink |}}
=== (A1) ===
Implementiere im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej in der Klasse ''StandaloneMerge'' das Zusammenführen der beiden Teilarrays a und b in der Methode ''merge()'' (ohne Parameter). Die Hinweise sind gestufte Hilfen, die du bei Problemen nacheinander ansehen kannst.
++++ Hinweis 1: | Da die Eingabe bereits in zwei Teilarrays erfolgt, entfällt der Kopiervorgang aus dem Beispiel - du kannst direkt aus den Arrays a und b in das Array merged einfügen.
++++
++++ Hinweis 2: |
// Das sind die Indizes für die beiden Teilarrays
// Beide beginnen bei 0
int i=0;
int j=0;
// k läuft von 0 bis merged-length-1
// bei jedem Durchlauf muss ein neues Element eingefügt werden -
// nur welches?
// Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b!
for(int k=0; k
++++
++++ Hinweis 3: |
// Das sind die Indizes für die beiden Teilarrays
// Beide beginnen bei 0
int i=0;
int j=0;
// k läuft von 0 bis merged-length-1
// bei jedem Durchlauf muss ein neues Element eingefügt werden -
// nur welches?
// Es müssen 4 Fälle unterschieden werden. Denke an die Länge der Arrays a und b!
for(int k=0; k= a.length) {
// Fall 2: j ist außerhalb der Länge von b
} else if(j >= b.length) {
// Fall 3:
} else if() {
// Fall 4:
} else {
}
}
++++
++++ Hinweis 4: |
int i=0;
int j=0;
for(int k=0; k= a.length) {
// Das Array a ist abgearbeitet, jetzt können die Elemente
// von b ohne weiteres nach merged übertragen werden, weil a und b
// ja sortiert sind! Der Index von b muss jeweils erhöht werden.
merged[k] = b[j];
j++;
} else if(j >= b.length) {
// Das Array b ist abgearbeitet, jetzt können die Elemente
// von b ohne weiteres nach merged übertragen werden, weil a und b
// ja sortiert sind!
merged[k] = a[i];
i++;
} else if(less(b[j], a[i])) {
// Was fehlt hier?
} else {
// Was fehlt hier?
}
}
++++
++++ Lösungsvorschlag | Wenn du auf den Lösungsvorschlag zurückgreifen musstest: Kommentiere den Lösungsvorschlag ausführlich, um dir klarzumachen, was hier geschieht!
int i=0;
int j=0;
for(int k=0; k= a.length) {
merged[k] = b[j++];
} else if(j >= b.length) {
merged[k] = a[i++];
} else if(less(b[j], a[i])) {
merged[k] = b[j++];
} else {
merged[k] = a[i++];
}
}
++++
----
{{:aufgabe.png?nolink |}}
=== (A2) ===
Gib zunächst **getrennt** den Aufwand der Splitphase und der Mergephase in O-Notation an und begründe deine Aussage. Überlege dann, wie daraus abgeleitet der generelle Aufwand für den gesamten Mergesort-Algorithmus ist.
===== Mergesort: Versuch 1 =====
----
{{:aufgabe.png?nolink |}}
=== (A3) Naiver Mergesort ===
Implementiere unter Verwendung der oben implementierten //merge//-Methode einen naiven Mergesort-Algorithmus in der Methode ''public String[] msort(String[] a)''. Eine Vorlage findest du im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej in der Klasse ''MergeSortNaiv''. Eine Methode ''public String[] merge(String[] s, String[] t)'' ist entsprechend bereits implementiert.
Orientiere dich an folgendem Pseudocode:
msort: String[] a
wenn a.laenge ist 1:
return a
ende wenn
mitte = a.lange/2
ta1=teilarray von a von 0 bis mitte-1
ta2=teilarray von mitte bis a.laenge-1
return merge(msort(ta1), msort(ta2))
* Teste den Algorithmus
* Bewerte die Implementation in Hinsicht auf Ressourcenverbrauch und Effizienz
===== Arrayerzeugung ist teuer =====
Prinzipiell funktioniert unser "naiver Mergesort", jedoch ist die häufig auftretende Operation der Arrayerzeugung und das Hineinkopieren der Array-Elemente beim Teilen des Arrays teuer und sollte vermieden werden.
==== Merge reloaded ====
Wir befassen uns zunächst nochmal mit dem Merge-Vorgang und implementieren mit unseren Kenntnissen vom ersten Versuch die Methode
public void merge(String[] a, String[] speicher, int min, int mitte, int max)
in der Klasse ''StandaloneMerge''. Um diese Methode aufrufen zu können, müssen wir die beiden Arrays a und b im Konstruktor zusammenfügen und außerdem ein Speicherarray derselben Länge erzeugen, das man dem Methodenaufruf mitgeben kann.
----
{{:aufgabe.png?nolink |}}
=== (A4) ===
* Vollziehe das Zusammenfügen der Arrays, das Erzeugen des Speicher-Arrays und die Bestimmung den Methodenparameter nach.
* Entferne die Kommentarzeichen vor dem Methodenaufruf im Konstruktor.
Der "Kniff" ist später, dass man das Speicher-Array vor den rekursiven Aufrufen nur einmal erzeugt und dann mit den Parametern min, mitte und max steuert, welche Bereiche des Arrays zusammengefügt werden sollen. So muss man nicht in der Rekursion neue Arrays erzeugen, wie beim naiven Ansatz.
Es ist also wichtig, beim Übertragen der Elemente ins Speicher-Array in der merge Methode bei ''min'' zu beginnen und bei ''max'' zu enden, ebenso wie die beiden Indizes ''i'' und ''j'' bei ''min'' und bei ''mitte+1'' beginnen:
public void merge(String[] a, String[] speicher, int min, int mitte, int max) {
// Übertragen der Elemente von min bis max in
// das bereits vorhandene Speicherarray
for(int i=min; i<=max;i++) {
speicher[i]=a[i];
}
int i=min;
int j=mitte+1;
for(int k=min; k<=max; k++) {
// Die vier Fälle von oben
}
System.out.print("In einem Speicherarray: ");
System.out.println(Arrays.toString(a));
}
----
{{:aufgabe.png?nolink |}}
=== (A5) ===
Vervollständige die Implementierung, indem du die vier Fälle passend in die neue Methode überträgst.
===== Mergesort mit einem Speicher =====
Unter Verwendung der neuen Merge-Methode können wir jetzt eine Mergesort Implementation erzeugen, die nicht in jedem Rekursionsschritt neue Arrays erzeugen muss.
{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:mergesort1.drawio.png |}}
----
{{:aufgabe.png?nolink |}}
=== (A7) ===
Im BlueJ-Projekt findest du eine Methode MergeSort, in der dieses Vorgehen vorbereitet ist. Vervollständige die Implementation.
===== Material =====
{{simplefilelist>:faecher:informatik:oberstufe:algorithmen:sorting:mergesort:*}}