faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [15.02.2023 20:09] – [Merge reloaded] Frank Schiebelfaecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [13.02.2025 07:22] (aktuell) – Frank Schiebel
Zeile 10: Zeile 10:
 ===== Grundsätzliche Funktionsweise ===== ===== 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).   * **Teile** das Array in zwei Hälften (Divide).
   * Sortiere (**rekursiv**) die beiden Hälften (Sort).   * 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) ===  === (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.  ++++ 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; 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 - // bei jedem Durchlauf muss ein neues Element eingefügt werden -
 // nur welches?      // nur welches?     
Zeile 88: Zeile 88:
 int j=0; 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 - // bei jedem Durchlauf muss ein neues Element eingefügt werden -
 // nur welches?      // nur welches?     
Zeile 97: Zeile 97:
 // Fall 1 und 2 müssen überprüfen, ob sich die  // Fall 1 und 2 müssen überprüfen, ob sich die 
 // Indizes von a und b im erlaubten Bereich befinden. // 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?  // 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> <code java>
 int i=0; int i=0;
Zeile 174: Zeile 174:
 === (A2) ===  === (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 ===== ===== Mergesort: Versuch 1 =====
Zeile 196: Zeile 195:
   mitte = a.lange/2   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))   return merge(msort(ta1), msort(ta2))
Zeile 206: Zeile 205:
   * Bewerte die Implementation in Hinsicht auf Ressourcenverbrauch und Effizienz   * 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 ===== ===== 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 ==== ==== Merge reloaded ====
  
 Wir befassen uns zunächst nochmal mit dem Merge-Vorgang und implementieren mit unseren Kenntnissen vom ersten Versuch die Methode  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)    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  |}} {{: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> <code java>
Zeile 242: Zeile 269:
  
         for(int k=min; k<=max; k++) {         for(int k=min; k<=max; k++) {
-            if(i > mitte) { +         // Die vier Fälle von oben
-                a[k] = speicher[j++]; +
-            } else if(j > max) { +
-                a[k] = speicher[i++]; +
-            } else if(less(speicher[j], speicher[i])) { +
-                a[k] = speicher[j++]; +
-            } else { +
-                a[k] = speicher[i++]; +
-            }     +
         }         }
  
Zeile 258: Zeile 276:
     }     }
 </code> </code>
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A5) === 
 +
 +Vervollständige die Implementierung, indem du die vier Fälle passend in die neue Methode überträgst.
 +
 +===== Mergesort mit einem Speicher =====
 +
 +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 |}}
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A7) === 
 +
 +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:*}} 
  • faecher/informatik/oberstufe/algorithmen/sorting/mergesort/start.1676491793.txt.gz
  • Zuletzt geändert: 15.02.2023 20:09
  • von Frank Schiebel