Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [02.06.2025 16:32] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [03.06.2025 07:09] (aktuell) – [Zentrale Teilaufgabe: Merge] Frank Schiebel
@@ Zeile 57: / 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 83: / 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 101: / 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 123: / 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 152: / 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 171: / 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 233: / Zeile 244: @@
 </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 248: / Zeile 281: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A4) ===
+=== (A5) ===
   * Vollziehe das Zusammenfügen der Arrays, das Erzeugen des Speicher-Arrays und die Bestimmung den Methodenparameter nach.
@@ Zeile 280: / Zeile 313: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A5) ===
+=== (A6) ===
 Vervollständige die Implementierung, indem du die vier Fälle passend in die neue Methode überträgst.