Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [02.06.2025 17:12] – [Mergesort: Variante 1] 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;
+int ia = 0; // Zeiger auf das Element in Teilarray a
+int ib = 0; // Zeiger auf das Element in Teilarray b
-for(int k=0; k<merged.length; k++) {
+for(int im=0; im<merged.length; im++) {
-  if(i >= a.length) {
+  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 174: / Zeile 189: @@
 ===== Mergesort: Variante 1 =====
-Nachdem wir jetzt über eine funktionale Methode zum Zusammenfügen der Teilarrys verfügen, implementieren wir den gesamten Algorithmus, inklusive der rekursiven Aufrufe.
+Nachdem wir jetzt über eine funktionale Methode zum Zusammenfügen der Teilarrays verfügen, implementieren wir den gesamten Algorithmus, inklusive der rekursiven Aufrufe.
 ----
@@ Zeile 239: / Zeile 254: @@
   * An welchen Stellen im Baum wird ein merge-Vorgang ausgelöst?
-{{ :faecher:informatik:oberstufe:algorithmen:sorting:mergesort:mergesort.excalidraw.png |}}
+{{ :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.