Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [15.02.2023 20:44] – [Mergesort mit einem Speicher] Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [13.02.2025 07:22] (aktuell) – 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 49: / Zeile 49: @@
 === (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 62: / Zeile 62: @@
 int j=0;
-// k ist läuft von 0 bis merged-length-1
+// k läuft von 0 bis merged-length-1
 // bei jedem Durchlauf muss ein neues Element eingefügt werden -
 // nur welches?
@@ Zeile 88: / Zeile 88: @@
 int j=0;
-// k ist läuft von 0 bis merged-length-1
+// k läuft von 0 bis merged-length-1
 // bei jedem Durchlauf muss ein neues Element eingefügt werden -
 // nur welches?
@@ Zeile 97: / Zeile 97: @@
 // 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?
@@ Zeile 149: / Zeile 149: @@
 ++++
-++++ 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;
@@ Zeile 174: / Zeile 174: @@
 === (A2) ===
-Gib den Aufwand des Merge in O-Notation an und begründe deine Aussage.
+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 =====
@@ Zeile 196: / Zeile 195: @@
   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 206: / Zeile 205: @@
   * 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>
+++++
 ===== 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.
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A5) ===
+=== (A4) ===
-  * 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>
@@ Zeile 252: / Zeile 279: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A6) ===
+=== (A5) ===
 Vervollständige die Implementierung, indem du die vier Fälle passend in die neue Methode überträgst.
@@ Zeile 258: / Zeile 285: @@
 ===== Mergesort mit einem Speicher =====
-Unter Verwendung der neuen Merge-Methode können wir jetzt eine Metgesort Implementation erzeugen, die nicht in jedem Rekursionsschritt neue Arrays erzeugen muss.
+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 |}}
@@ Zeile 267: / Zeile 294: @@
 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:*}}