Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [06.02.2025 08:36] – [Grundsätzliche Funktionsweise] Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [03.06.2025 07:09] (aktuell) – [Zentrale Teilaufgabe: Merge] Frank Schiebel
@@ 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 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 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 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
@@ Zeile 100: / Zeile 105: @@
 // 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 151: / Zeile 157: @@
 ++++ 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>
@@ Zeile 170: / Zeile 186: @@
-----
-{{: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 =====
+===== 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 204: / 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 =====
@@ Zeile 212: / Zeile 273: @@
 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 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) ===
+=== (A5) ===
   * Vollziehe das Zusammenfügen der Arrays, das Erzeugen des Speicher-Arrays und die Bestimmung den Methodenparameter nach.
@@ Zeile 251: / Zeile 313: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A5) ===
+=== (A6) ===
 Vervollständige die Implementierung, indem du die vier Fälle passend in die neue Methode überträgst.