Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [25.05.2023 12:33] – [Mergesort mit einem Speicher] sron
+++ faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [03.06.2025 07:09] (aktuell) – [Zentrale Teilaufgabe: Merge] Frank Schiebel
@@ Zeile 10: / Zeile 10: @@
 ===== Grundsätzliche Funktionsweise =====
-Mergesort ist eine Divide-and-Conquer Algorithmus, der prinzipiell folgendermaßen funktioniert:
+Mergesort ist eine [[faecher:informatik:oberstufe:algorithmen:rekursion:teile_und_herrsche:start|Divide-and-Conquer]](("Teile und herrsche")) 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 einen sortierten Array **zusammen** (Merge).
+  * **Füge** die beiden Hälften wieder zu einem sortierten Array **zusammen** (Merge / Conquer).
@@ Zeile 22: / Zeile 22: @@
 ===== 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.
+Bevor wir den gesamten Algorithmus betrachten, wollen wir uns zunächst nur mit dem Schritt des korrekten Zusammenfügens zweier sortierter Teilarrays zu einem sortierten Array beschäftigen, denn dort findet die eigentliche "Sortierarbeit" bei MergeSort statt.\\
+Wir schauen also an einem Beispiel nochmal etwas genauer, wie man diesen Vorgang verstehen und implementieren kann.
-Gegeben sind also zwei sortierte Teilarrays, die zu einem sortierten Array zusammengefügt werden sollen:
+Gegeben sind zwei **sortierte** Teilarrays, die zu einem **sortierten** Array zusammengefügt werden sollen:
 {{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:merge.drawio.png |}}
@@ Zeile 49: / Zeile 50: @@
 === (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. Die Hinweise sind gestufte Hilfen, die du bei Problemen nacheinander ansehen kannst.
+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.
@@ Zeile 56: / Zeile 57: @@
 ++++ Hinweis 2: |
 <code java>
+merged = new String[a.length + b.length];
 // Das sind die Indizes für die beiden Teilarrays
 // Beide beginnen bei 0
-int i=0;
+int ia = 0; // Zeiger auf das Element in Teilarray a
-int j=0;
+int ib = 0; // Zeiger auf das Element in Teilarray b
-// k ist läuft von 0 bis merged-length-1
+// im 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<merged.length; k++) {
+for(int im=0; im<merged.length; im++) {
 // Fall 1:
@@ Zeile 82: / Zeile 86: @@
 ++++ Hinweis 3: |
 <code java>
+merged = new String[a.length + b.length];
 // Das sind die Indizes für die beiden Teilarrays
 // Beide beginnen bei 0
-int i=0;
+int ia = 0; // Zeiger auf das Element in Teilarray a
-int j=0;
+int ib = 0; // Zeiger auf das Element in Teilarray b
-// k ist läuft von 0 bis merged-length-1
+// im 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<merged.length; k++) {
+for(int im=0; im<merged.length; im++) {
 // Fall 1 und 2 müssen überprüfen, ob sich die
 // Indizes von a und b im erlaubten Bereich befinden.
-// Was bedeutet das, wenn der INdex außerhalb des erlaubten Bereichs ist?
+// Was bedeutet das, wenn der Index außerhalb des erlaubten Bereichs ist?
 // Was muss dann geschehen?
-  // Fall 1: i ist außerhalb der Länge von a
+  // Fall 1: ia ist außerhalb der Länge von a
-  if(i >= a.length) {
+  if(ia >= a.length) {
-  // Fall 2:  j ist außerhalb der Länge von b
+  // Fall 2:  ib ist außerhalb der Länge von b
-  } else if(j >= b.length) {
+  } else if(ib >= b.length) {
   // Fall 3:
@@ Zeile 122: / Zeile 126: @@
 ++++ Hinweis 4: |
 <code java>
-int i=0;
+merged = new String[a.length + b.length];
-int j=0;
-for(int k=0; k<merged.length; k++) {
+int ia = 0; // Zeiger auf das Element in Teilarray a
-  if(i >= a.length) {
+int ib = 0; // Zeiger auf das Element in Teilarray b
+for(int im=0; im<merged.length; im++) {
+  if(ia >= 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];
+    merged[im] = b[ib];
-    j++;
+    ib++;
-  } else if(j >= b.length) {
+  } else if(ib >= 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];
+    merged[im] = a[ia];
-    i++;
+    ia++;
-  } else if(less(b[j], a[i])) {
+  } else if(less(b[ib], a[ia])) {
     // Was fehlt hier?
   } else {
@@ Zeile 149: / Zeile 155: @@
 ++++
-++++ Lösungsvorschlag | Wenn du auf den Lösungsvorschlag zurückgreifen musstest: Kommentiere den Lösungsvorschlag ausführlich, um dir klar zu machen, was hier geschieht!
+++++ Lösungsvorschlag | Wenn du auf den Lösungsvorschlag zurückgreifen musstest: Kommentiere den Lösungsvorschlag ausführlich, um dir klarzumachen, was hier geschieht!
 <code java>
-int i=0;
+merged = new String[a.length + b.length];
-int j=0;
+int ia = 0; // Zeiger auf das Element in Teilarray a
-for(int k=0; k<merged.length; k++) {
+int ib = 0; // Zeiger auf das Element in Teilarray b
-  if(i >= a.length) {
-     merged[k] = b[j++];
+// im zeigt auf das zu besetzende Element im gemergten Array merged
-  } else if(j >= b.length) {
+for(int im = 0; im < merged.length; im++) {
-     merged[k] = a[i++];
+   // a ist schon komplett in merged - kopiere die Elemente von b
-  } else if(less(b[j], a[i])) {
+   if(ia >= a.length) {
-      merged[k] = b[j++];
+       merged[im] = b[ib];
-  } else {
+       ib++;
-      merged[k] = a[i++];
+   } else if (ib >= b.length) { // b ist schon komplett in merged - kopiere Elemente von a
-  }
+       merged[im] = a[ia];
+       ia++;
+   } else if(less(a[ia],b[ib])) { // a[ia] ist das aktuell kleinere - kopiere nach merged
+        merged[im] = a[ia];
+        ia++;
+    } else { // b[ib] ist kleiner - kopiere nach merged
+        merged[im] = b[ib];
+        ib++;
+    }
 }
 </code>
 ++++
-----
-{{:aufgabe.png?nolink  |}}
-=== (A2) ===
-Gib den Aufwand des Merge in O-Notation an und begründe deine Aussage.
-===== Mergesort: Versuch 1 =====
+===== Mergesort: Variante 1 =====
+Nachdem wir jetzt über eine funktionale Methode zum Zusammenfügen der Teilarrays verfügen, implementieren wir den gesamten Algorithmus, inklusive der rekursiven Aufrufe.
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A3) Naiver Mergesort ===
+=== (A2) Naiver Mergesort: Implementation ===
 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.
@@ Zeile 196: / Zeile 207: @@
   mitte = a.lange/2
-  ta1=teilarray von a von 0 bis mitte
+  ta1=teilarray von a von 0 bis mitte-1
-  ta2=teilarray von mitte+1 bis a.laenge-1
+  ta2=teilarray von mitte bis a.laenge-1
   return merge(msort(ta1), msort(ta2))
@@ Zeile 205: / Zeile 216: @@
   * Teste den Algorithmus
   * Bewerte die Implementation in Hinsicht auf Ressourcenverbrauch und Effizienz
+++++ Lösungsvorschlag |
+<code java>
+// Mergesort naiv
+    public String[] msort(String[] a) {
+        // Implementiere hier gemäß des Pseudocodes im Wiki
+        if(a.length == 1) {
+            return a;
+        }
+        int mitte = a.length/2;
+        // Dieser Schritt ist aufwändig!
+        // Man muss Arrays erzeugen und alle Elemente
+        // in die neuen Teilarrays hineinkopieren.
+        // das ist O(n) bei jedem Aufruf :(
+        String[] ta1 = new String[mitte];
+        String[] ta2 = new String[a.length-mitte];
+        for(int i=0; i<mitte; i++) {
+            ta1[i]=a[i];
+        }
+        for(int i=mitte; i<a.length;i++) {
+            ta2[i-mitte] = a[i];
+        }
+        return merge(msort(ta1),msort(ta2));
+    }
+</code>
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) Naiver Mergesort: Aufrufbaum ===
+**(A)** Der folgende Aufrufbaum stellt dar, wie das Array ''String[] a = { "9", "4,", "3", "8", "1"} '' sortiert wird.
+  * In welcher Reihenfolge finden die Aufrufe der Funktion ''msort'' statt?
+  * An welchen Stellen im Baum wird ein merge-Vorgang ausgelöst?
+{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:mergesort.excalidraw.png?600 |}}
+++++ Lösung | {{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:mergesort-animate.svg |}} ++++
+**(B)** Gegeben ist der folgende String, der sortiert werden soll: ''String[] a =  {"F", "Z", "K", "A", "C" }''. Zeichne einen Aufrufbaum für diesen Vorgang.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+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.
 ===== 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.
+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
+<code java>
   public void merge(String[] a, String[] speicher, int min, int mitte, int max)
+</code>
-in der Vorlage //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.
+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.
 ----
@@ Zeile 222: / Zeile 283: @@
 === (A5) ===
-  * Vollziehe das Zusammenfügen der Arrays, das Erzeugen des Speicher-Arrays und die Bestimmung den Methodenparameter nach
+  * 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
+  * Entferne die Kommentarzeichen vor dem Methodenaufruf im Konstruktor.
-Der "Kniff" ist später, dass man das Speicher-Array später 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.
+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-Arrays 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:
+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:
 <code java>