Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [07.02.2024 09:39] – [Arrayerzeugung ist teuer] 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 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 =====
@@ Zeile 213: / Zeile 239: @@
 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 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.