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:15] – [Zentrale Teilaufgabe: Merge] Frank Schiebelfaecher:informatik:oberstufe:algorithmen:sorting:mergesort:start [29.02.2024 10:58] (aktuell) – [Zentrale Teilaufgabe: Merge] Marco Kuemmel
Zeile 14: Zeile 14:
   * **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 =====
  
  
Zeile 181: Zeile 183:
 === (A3) Naiver Mergesort ===  === (A3) Naiver Mergesort === 
  
-Implementiere unter Verwendung der oben implementierten //merge//-Methode einen naiven Mergesort-Algorithmus in der Methode ''public String[] msort(String[] a)''. Eine Vorlage findest du im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej in der Klasse ''MergeSortNaiv''. Eine Methode 'public String[] merge(String[] s, String[] t)'' ist entsprechend bereits implementiert.+Implementiere unter Verwendung der oben implementierten //merge//-Methode einen naiven Mergesort-Algorithmus in der Methode ''public String[] msort(String[] a)''. Eine Vorlage findest du im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej in der Klasse ''MergeSortNaiv''. Eine Methode ''public String[] merge(String[] s, String[] t)'' ist entsprechend bereits implementiert.
  
 Orientiere dich an folgendem Pseudocode: Orientiere dich an folgendem Pseudocode:
Zeile 193: 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 202: Zeile 204:
   * Teste den Algorithmus   * Teste den Algorithmus
   * Bewerte die Implementation in Hinsicht auf Ressourcenverbrauch und Effizienz   * Bewerte die Implementation in Hinsicht auf Ressourcenverbrauch und Effizienz
 +
 +===== 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.
 +
 +==== Merge reloaded ====
 +
 +Wir befassen uns zunächst nochmal mit dem Merge-Vorgang und implementieren mit unseren Kenntnissen vom ersten Versuch die Methode 
 +
 +  public void merge(String[] a, String[] speicher, int min, int mitte, int max) 
 +  
 +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  |}}
 +=== (A4) === 
 +
 +  * 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.
 +
 +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-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>
 +public void merge(String[] a, String[] speicher, int min, int mitte, int max) {
 +
 +        // Übertragen der Elemente von min bis max in 
 +        // das bereits vorhandene Speicherarray
 +        for(int i=min; i<=max;i++) {
 +            speicher[i]=a[i];
 +        }
 +
 +        int i=min;
 +        int j=mitte+1;
 +
 +        for(int k=min; k<=max; k++) {
 +         // Die vier Fälle von oben
 +        }
 +
 +        System.out.print("In einem Speicherarray: ");
 +        System.out.println(Arrays.toString(a));
 +    }
 +</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.1676488559.txt.gz
  • Zuletzt geändert: 15.02.2023 20:15
  • von Frank Schiebel