Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [06.02.2024 12:21] – [Merge reloaded] Marco Kuemmel
+++ 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).
@@ 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.
 ----
@@ Zeile 222: / Zeile 249: @@
 === (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>