Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [06.02.2024 12:23] – [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.
 ----