MergeSort rekursiv programmieren

[Tiger87]

Hallo Forengemeinde,

ich soll MergeSort rekursiv programmieren. Die Methodensignatur darf dabei nicht verändert werden.
Mein geschriebender Code kann mit einem Array a[7 5 3 1] momentan:

Schritt 1:
b [7 5] #### e[3 1]

Erneuter Methodenaufruf mit b
Schritt2
b[7] #### e[5] ####

merge
c[5 7]

Das Zurückspringen auf Stelle 1 klappt nicht um die Methode auch mit e auszuführen.
Habt ihr einen Tipp für mich?


Hinweis:
Ich lerne momentan die Java Algorithmen und habe erst im nächsten Jahr Objektorientierte Programmierung.

import AlgoTools.IO; = Uni interne Klasse zum einlesen und ausgeben

import AlgoTools.IO;
public class MergeSort {
  private static int schritte = 0; 
  
  public static void main(String[] args) {
    int laenge = 0;
    int []d;
    // Lese Array ein
    do {
      laenge = IO.readInt("Laenge des Array: ");
    } while(laenge <= 0);
    // Lege Array an, welches ausgegeben wird
    int[]a= new int[laenge];  
    // lies Zeile mit korrekter Anzahl von Buchstaben ein
    do {
      a = IO.readInts("Bitte Zahlenfolge eingeben   ");
    } while(a.length != laenge);
    
    d = sortRekursiv(a); 
    for (int i = 0;i < d.length;i++) {
      IO.print(d[i]);
    } // end of for 
  }
  
  //Array immer in zwei haelften Teilen bis nur noch Arrays mit zweit Zahlen Uebrig bleiben
  //Dann Teilstücke sortieren und zusammensetzen
  public static int[] sortRekursiv(int[] a) {
    //Array teilen
    //Teilarray b anlegen   
    int[]b = new int[(a.length/2)];
    
    
    if (a.length%2 == 1) { // Wenn Rest von a ungerade ist
      //Teilarray e anlegen 
      int[]e = new int[((a.length/2)+1)];
      IO.println("Länge b   "+b.length);
      IO.println("Länge c   "+e.length);
      //Daten kopieren
      //a kopieren in b
      for (int i = 0; i< b.length ;i++ ) {
        b[i] = a[i];
      } // end of for
      IO.print("Array b   ");
      for (int i =0;i<b.length ;i++ ) {
        IO.print(b[i]);
      } // end of for
      IO.println();
      
      //a kopieren in e
      for (int i = 0, j = (b.length); i < e.length|| j < a.length;i++, j++ ) {
        e[i] = a[j];
      }
      IO.print("Array e   ");
      for (int i =0;i<e.length ;i++ ) {
        IO.print(e[i]);
      } // end of for
      IO.println();
      
      if (b.length == 1 && e.length == 1) {// Größe der Teilstücke 1
        return merge (b,e); //Sortier beide Teilstücke zu einem Array
      } else {    
        if (b.length > 1){    // Wenn Teilstück b noch größer 1 
          return sortRekursiv(b);
        } else {              // Wenn Teilstück c noch größer 1 
          //throw new RuntimeException("Überprüfung");
          return sortRekursiv(e);
        }
      }   
    } else {  // Wenn Rest von e gerade ist
      //Teilarray c anlegen 
      int[]e = new int[((a.length/2))];
      IO.println("Länge b   "+b.length);
      IO.println("Länge e   "+e.length);
      
      //Daten kopieren
      //a kopieren in b
      for (int i = 0; i< b.length ;i++ ) {
        b[i] = a[i];
      } // end of for
      IO.print("Array b   ");
      for (int i =0;i<b.length ;i++ ) {
        IO.print(b[i]);
      } // end of for
      IO.println();
      
      //a kopieren in e
      for (int i = 0, j = (b.length); i < e.length || j < a.length;i++, j++ ) {
        e[i] = a[j];
      }
      IO.print("Array e   ");
      for (int i =0;i<e.length ;i++ ) {
        IO.print(e[i]);
      } // end of for
      IO.println();
      
      schritte = schritte +1;
      
      if (b.length == 1 && e.length == 1) {  // Größe der Teilstücke 1
        return merge (b,e);   //Sortier beide Teilstücke zu einem Array
      } else {    
        if (b.length > 1){          // Wenn Teilstück b noch größer 1 
          return sortRekursiv(b);
        } else {                    // Wenn Teilstück e noch größer 1 
          //throw new RuntimeException("Überprüfung");
          return sortRekursiv(e);
        }
      }   
    } // end of if-else
  }  
  
  
  
  public static int[] merge (int[]a, int[]b) {   // mischt a und b
    // liefert Ergebnis zurueck
    
    int i=0, j=0, k=0;                           // Laufindizes
    int[] c = new int[a.length + b.length];      // Platz fuer Folge c besorgen
    
    while ((i<a.length) && (j<b.length)) {       // mischen, bis ein Array leer
      if (a[i] < b[j])                           // jeweils das kleinere Element
      c[k++] = a[i++];                       // wird nach c uebernommen
      else
      c[k++] = b[j++];
    } 
    while (i<a.length) c[k++] = a[i++];          // ggf.: Rest von Folge a
    while (j<b.length) c[k++] = b[j++];          // ggf.: Rest von Folge b
    
    return c;                                    // Ergebnis abliefern
  }   
}

 

[Tiger87]

War vielleicht zu unübersichtlich. Habe mal nur den Code der relvanten Methode gepostet mit verständlichen Variablennamen. Sorry 😳

  //Array immer in zwei haelften Teilen bis nur noch Arrays mit zweit Zahlen Uebrig bleiben
  //Dann Teilstücke sortieren und zusammensetzen
  public static int[] sortRekursiv(int[] a) {
    //Array teilen
    //Teilarray links anlegen   
    int[]links = new int[(a.length/2)];
    
    
    if (a.length%2 == 1) { // Wenn Rest von a ungerade ist
      //Teilarray rechts anlegen 
      int[]rechts = new int[((a.length/2)+1)];
      
      //Daten kopieren
      //a kopieren in links
      for (int i = 0; i< links.length ;i++ ) {
        links[i] = a[i];
      } 
      
      //a kopieren in e
      for (int i = 0, j = (links.length); i < rechts.length|| j < a.length;i++, j++ ) {
        rechts[i] = a[j];
      }
      
      if (links.length == 1 && rechts.length == 1) {// Größe der Teilstücke 1
        return merge (links,rechts); //Sortier beide Teilstücke zu einem Array
      } else {    
        if (links.length > 1){    // Wenn Teilstück b noch größer 1 
          return sortRekursiv(links);
        } else {              // Wenn Teilstück c noch größer 1 
          return sortRekursiv(rechts);
        }
      }   
    } else {  // Wenn Rest von rechts gerade ist
      //Teilarray rechts anlegen 
      int[]rechts = new int[((a.length/2))];

      //Daten kopieren
      //a kopieren in links
      for (int i = 0; i< rechts.length ;i++ ) {
        links[i] = a[i];
      } 
      
      //a kopieren in rechts
      for (int i = 0, j = (links.length); i < rechts.length || j < a.length;i++, j++ ) {
        rechts[i] = a[j];
      }
      
      if (links.length == 1 && rechts.length == 1) {  // Größe der Teilstücke 1
        return merge (links,rechts);   //Sortier beide Teilstücke zu einem Array
      } else {    
        if (links.length > 1){          // Wenn Teilstück links noch größer 1 
          return sortRekursiv(links);
        } else {                    // Wenn Teilstück rechts noch größer 1 
          return sortRekursiv(rechts);
        }
      }   
    } 
  }

 

[minzee]

Das hat sich vermutlich deshalb noch niemand angeschaut, weil das ziemlich kompliziert ausschaut. Du solltest das zuerst mal vereinfachen.

Das Aufteilen kann auf 2erlei Varianten passieren:

- Variante 1:
Man teilt das Array in 2 Arrays auf und übergibt sie den rekursiven Methodenaurufen.

- Variante 2:
Man definiert 2 int-Werte, die auf bestimmte Stellen des Arrays zeigen: left und right.
Diese übergibt man dann den rekursiven Methodenaufrufen.
left und right definieren den Bereich, der genauer untersucht werden soll.

Das Zusammenführen kann ebenfalls auf 2erlei Varianten passieren, wobei es davon abhängt, wie man aufgeteilt hat.

- zu Variante 1:
Man muss die 2 Teilarrays (die dann schon vorsortiert sind) wieder zu 1 Array zusammenführen.

- zu Variante 2:
Man definiert ein Hilfsarray, in dem die vorsortierten Arraybereiche zusammenkopiert werden.
Die Elemente dieses Hilfsarrays fügt man dann sortiert an den richtigen Positionen in das eigentliche Array ein.

Die Laufbedingungen für die rekursiven Aufrufe hängen wieder von der gewählten Variante ab.

- zu Variante 1:
Ein weiteres Aufteilen und Zusammenführen erfolgt nur dann, wenn es noch mehr als 1 Element im übergebenen Array gibt.

zu Variante 2:
Hier wird man nur aktiv, wenn left < right ist.

 

[minzee]

Hier ein ungetesteter Code zur Variante 1 (ungetestet, weil ich hier keine fertigen Programme reinposten soll):

public static void sort(int[] a)
{
   int length = a.length;
   if(length > 1) // Laufbedingung
   {
      // Aufteilen:
      int half = (int)(length / 2);  
      int[] aLeft = copyOfRange(a, 0, half);  
      int[] aRight = copyOfRange(a, half, length);
      sort(aLeft); // sortiert aLeft vor
      sort(aRight); // sortiert aRight vor
      
      // Zusammenführen:
      int lengthLeft = aLeft.length;
      int lengthRight = aRight.length;
      int left = 0; // durchläuft das linke Array von links nach rechts
      int right = 0; // durchläuft das rechte Array von links nach rechts
      int i = 0;
      int min = Math.min(lengthLeft, lengthRight);
      while(i < min) // vergleichbare Elemente
      {
         if(aLeft[left] <= aRight[right])
         {
            a[i] = left[left++];
         }
         else
         {
            a[i] = right[right++];
         }
         ++i;
      }
      while(left < lengthLeft) // restlichen linken Elemente
      {
         a[i++] = aLeft[left++];
      }
      while(right < lengthRight) // restlichen rechten Elemente
      {
         a[i++] = aRight[right++];
      }
   }
}

Stecken vermutlich noch einige Fehler darin.

 

[minzee]

Und hier Variante 2:

/**
 * @param int left Bereich linker Rand
 * @param int right Bereich rechter Rand
 */
private static void sort(int[] a, int left, int right)
{
   if(left < right) // Laufbedingung
   {
      // Aufteilen:
      int half = (int)((left + right) / 2);
      sort(a, left, half); // sortiert den Teilbereich von left bis half vor
      sort(a, half + 1, right); // sortiert den Teilbereich von half + 1 bis right vor
      
      // Zusammenführen:
      int[] aSort = new int[right - left + 1];
      for(int i = left; i <= half; ++i) // linken Bereich links in aSorted reinkopieren
      {
         aSort[i] = a[i];
      }
      for(int i = half + 1; i <= right; ++i) // rechten Bereich rechts im umgekehrter Reihenfolge in aSorten reinkopieren
      {
         aSort[right - (i - (half + 1))] = a[i];
      }
      int i = left;
      while(left <= right) // left und right bewegen sich dann aufeinander zu
      {
         if(aSort[left] < aSort[right])
         {
            a[i] = aSort[left++];
         }
         else
         {
            a[i] = aSort[right--];
         }
         ++i;
      }
   }
}
public static void sort(int[] a)
{
   sort(a, 0, a.length - 1);
}

Ebefalls ungetestet und vermutlich auch wieder mit Fehlern.

 

[minzee]

Falls wer diese beiden Varianten testet, würden mich dann die fertigen Programme interessieren 😉

 

[Tiger87]

Vielen Dank für deine Hilfe. Innerhalb von einer Stunde um 4 Nachts zwei Quellcodes zu schreiben, Respekt. Allerdings kann ich so deine Methoden nicht benutzen, da sie wegen void nicht Rekursiv sind und wir einige Befehle noch nicht hatten, also nicht benutzen dürfen. Außerdem darf ich die Methodensignatur nicht verändern. Aber deine Ideen sind interessant. Die werde ich mir in Ruhe ansehen. Vielen Dank nochmal.

 

[minzee]

Eure Variante scheint mir wie meine Variante 1 zu sein. Allerdings erscheint mir eure Variante ziemlich unlogisch, weil scheinbar noch ein zusätzliches Array angelegt werden muss. Aber ich vermute, das ist nur zu Übungszwecken.

sort liefert also ein Array zurück. D. h. man bekommt durch die 2 rekursiven Aufrufe 2 Arrays. D. h. anstatt alles in a zusammenzuführen, muss du jetzt ein neues Array anlegen und die 2 Arrays vom rekursiven Aufruf darin zusammenführen. Zumindest vermute ich, dass das so geht.

Mir ist übrigens schon ein Fehler aufgefallen. Im der Variante 1, wo ich mit min arbeite, ist die Definition der Schleifenbedingung falsch. Dort sollte stehen: while(left < aLeft.length && right < aRight.length)

public static void sort(int[] a)
{
   int length = a.length;
   if(length > 1) // Laufbedingung
   {
      // Aufteilen:
      int half = (int)(length / 2);
      int[] aLeft = copyOfRange(a, 0, half);
      int[] aRight = copyOfRange(a, half, length);
      sort(aLeft); // sortiert aLeft vor
      sort(aRight); // sortiert aRight vor

      // Zusammenführen:
      int lengthLeft = aLeft.length;
      int lengthRight = aRight.length;
      int left = 0; // durchläuft das linke Array von links nach rechts
      int right = 0; // durchläuft das rechte Array von links nach rechts
      int i = 0;
      while(left < aLeft.length && right < aRight.length) // vergleichbare Elemente
      {
         if(aLeft[left] <= aRight[right])
         {
            a[i] = left[left++];
         }
         else
         {
            a[i] = right[right++];
         }
         ++i;
      }
      while(left < lengthLeft) // restlichen linken Elemente
      {
         a[i++] = aLeft[left++];
      }
      while(right < lengthRight) // restlichen rechten Elemente
      {
         a[i++] = aRight[right++];
      }
   }
}

Deine Variante müsste dann irgendwie so aussehen:

public static int[] sort(int[] a)
{
   int length = a.length;
   if(length > 1) // Laufbedingung
   {
      // Aufteilen:
      int half = (int)(length / 2);
      int[] aLeft = copyOfRange(a, 0, half);
      int[] aRight = copyOfRange(a, half, length);
      aLeft = sort(aLeft); // sortiert aLeft vor
      aRight = sort(aRight); // sortiert aRight vor
      
      // Zusammenführen:
      int[] aSorted = new int[length];
      int lengthLeft = aLeft.length;
      int lengthRight = aRight.length;
      int left = 0; // durchläuft das linke Array von links nach rechts
      int right = 0; // durchläuft das rechte Array von links nach rechts
      int i = 0;
      while(left < aLeft.length && right < aRight.length) // vergleichbare Elemente
      {
         if(aLeft[left] <= aRight[right])
         {
            aSorted[i] = aLeft[left++];
         }
         else
         {
            aSorted[i] = aRight[right++];
         }
         ++i;
      }
      while(left < lengthLeft) // restlichen linken Elemente
      {
         aSorted[i++] = aLeft[left++];
      }
      while(right < lengthRight) // restlichen rechten Elemente
      {
         aSorted[i++] = aRight[right++];
      }
      return aSorted;
   }
   return a;
}

Wieder nicht getestet.

 

[Tiger87]

Das war die Lösung zur Aufgabe.

/******************************  MergeSort.java  ******************************/

import AlgoTools.IO;

/**
 * Sortierung eines Arrays von beliebig vielen Elementen mit dem rekursiven
 * Mergesort-Algorithmus.
 */
public class MergeSortRekursiv {

  private static int schritte;

  /**
   * Methode, die den rekursiven MergeSort implementiert.
   *
   * @param a
   *          zu sortierendes Array, wird innerhalb der Methode nicht veraendert
   * @return sortiertes Array
   */
  public static int[] sortRekursiv(int[] a) {

    int l = a.length / 2;              // Laenge der beiden Teilfolgen

    if (l == 0)
      return a;                        // eine einelementige Folge ist sortiert

    int[] b = new int[l];              // die beiden Teilfolgen
    int[] c = new int[a.length - l];

    for (int i = 0; i < l; i++) {
                                       // kopiere a in die Teilfolgen
      b[i] = a[i];                     // 1. Haelfte nach b

    }

    for (int i = l; i < a.length; i++) {
        c[i - l] = a[i];                 // 2. Haelfte nach c
    }

    // zurueckgegeben werden die beiden sortierten Teilfolgen gemischt
    return merge(sortRekursiv(b), sortRekursiv(c));
  }

  /**
   * Mischt zwei sortierte Arrays mit einer Laengendifferenz
   * von 0 oder 1 zu einem sortierten Array
   *
   * @param a Array a, wird nicht veraendert
   * @param b Array b, wird nicht veraendert
   *
   * @return gemischtes, sortiertes Array
   */
  public static int[] merge (int[]a, int[]b) {   // mischt a und b
                                                 // liefert Ergebnis zurueck

    int i=0, j=0, k=0;                           // Laufindizes
    int[] c = new int[a.length + b.length];      // Platz fuer Folge c besorgen

    while ((i<a.length) && (j<b.length)) {       // mischen, bis ein Array leer

      schritte++;

      if (a[i] < b[j])                           // jeweils das kleinere Element
          c[k++] = a[i++];                       // wird nach c uebernommen
      else
          c[k++] = b[j++];
    }

    // ggf.: Rest von Folge a
    while (i<a.length){
      schritte++;
      c[k++] = a[i++];
    }

    // ggf.: Rest von Folge b
    while (j<b.length){
      schritte++;
      c[k++] = b[j++];
    }

    return c;                                    // Ergebnis abliefern
  }

  /**
   * Liest ein int-Array ein und gibt es unter Angabe der Schrittzahl
   * sortiert wieder aus.
   */
  public static void main(String argv[]) {

    schritte = 0;
    int[] a;

    //Einlesen
    do {
      a = IO.readInts("Bitte die Zahlen: ");
    } while(a.length == 0);

    //Sortieren
    a = sortRekursiv(a);

    //Ausgabe
    IO.println("Die sortierte Folge:");
    for(int i = 0; i < a.length; i++) {
      IO.print(a[i] + "  ");
    }

    //Schrittzahl
    IO.println("\nMit Anzahl Schritten: " + schritte);

  }


}