Rekursion verstehen.

[emorej]

Guten Tag,

public int[] mergeSortCore(int[] a)

    {
        int[] linkeListe;
        int[] rechteListe;
      
        if(a.length <= 1)
        {
            return a;
        }
        else
        {
            linkeListe= linkeListe(a);
            rechteListe= rechteListe(a);
          
            linkeListe= mergeSortCore(linkeListe);
            rechteListe= mergeSortCore(rechteListe);  
          
            return merge(linkeListe, rechteListe);
        }

public int[] merge(int[] links, int[] rechts)
    {
  
        int[] mergeArray = new int[links.length*2];
        links = extendArray(links,links.length+1);
        rechts = extendArray(rechts,rechts.length+1);
        int k = 0;
        int j = 0;
        int i = 0;
        while(k<mergeArray.length &&i<links.length&&j<rechts.length) {
            if(links[i]<rechts[j]) {
                    mergeArray[k]=links[i];
                    k++;
                    i++;
            }
                else {
                    mergeArray[k]=rechts[j];
                    k++;
                    j++;
                }
              
        }
        return mergeArray;
    }

Ich verstehe das Prinzip der Rekursion nicht ganz. Die Methode merge(int[] links, int[] rechts) habe ich nur zum Verständnis mit reingepostet.

Mein Problem liegt bei der Methode mergeSortCore(int[] a). Also, wenn das Array eine Länge von 1 oder weniger hat, dann wird das Array a einfach ausgegeben. Sonst wird das Array linkeListe und rechteListe erstellt. Also wird das Array a in zwei Teile gesplittet. Aber was soll nun dieses return merge(linkeListe, rechteListe)?

Also ich weiß, dass die Methode mergeSortCore(int[] a) das Array a so lange splitten soll bis nur noch Array der Länge 1 vorhanden sind und die werden dann der Methode merge() übergeben. Aber ich weiß einfach nicht, wie das in der Praxis funktioniert. Also wo sieht man, dass mergeSortCore das so lange splittet und erst bei a.length= 1 übergeben wird..?

Ich würde die Methode ohne Vorkenntnisse einfach so verstehen, dass das Array a einmal in zwei Teile gesplittet wird und dann der Methode merge() übergeben wird, dies ist aber nicht der Fall...

MfG

 

[mihe7]

Also wo sieht man, dass mergeSortCore das so lange splittet und erst bei a.length= 1 übergeben wird..?

Hier:

            linkeListe= mergeSortCore(linkeListe);
            rechteListe= mergeSortCore(rechteListe);

wird die zuvor erstellte linkeListe wieder gesplittet, danach die rechteListe. Da mergeSortCore sich selbst aufruft, passiert das so lange, bis a.length <= 1 gilt.

Aber was soll nun dieses return merge(linkeListe, rechteListe)?

Die linke und die rechte Liste sind jeweils sortiert - aber nur in sich. An der Stelle geht es einfach darum, die beiden Listen zu einer neuen, sortierten Liste zusammenzuführen. Also aus z. B. {10,20,30},{15,25,35} macht merge {10,15,20,25,30,35}.

 

[emorej]

Hier:

            linkeListe= mergeSortCore(linkeListe);
            rechteListe= mergeSortCore(rechteListe);

wird die zuvor erstellte linkeListe wieder gesplittet, danach die rechteListe. Da mergeSortCore sich selbst aufruft, passiert das so lange, bis a.length <= 1 gilt.


Die linke und die rechte Liste sind jeweils sortiert - aber nur in sich. An der Stelle geht es einfach darum, die beiden Listen zu einer neuen, sortierten Liste zusammenzuführen. Also aus z. B. {10,20,30},{15,25,35} macht merge {10,15,20,25,30,35}.

Aber mergeSortCore sortiert doch kein Array? Also 10,20,30 ist ja bereits sortiert, wo ist das passiert? Und wenn a.length <= 1 ist, dann wird doch das Array a einfach ausgegeben? Aber wohin? Oder ist das einfach die Syntax der Rekursion? Sieht nämlich so aus, als würde bei a.length <= 1 "return a" gemacht werden.

MfG

 

[mihe7]

Sieht nämlich so aus, als würde bei a.length <= 1 "return a" gemacht werden.

Das sieht nicht nur so aus, das ist so.

Nimm mal an, du fängst an mit mergeSortCore({40,20}). Die Länge ist größer als 1 also wird die Liste erstmal geteilt.

            linkeListe= linkeListe(a); // linkeListe = {40}
            rechteListe= rechteListe(a); // rechte Liste = {20}

Die nächste Zeile wird interessanter:

            linkeListe= mergeSortCore(linkeListe);

Dort wird zunächst mergeSortCore(linkeListe) aufgerufen. Die aktuelle Ausführung der aktuellen Methode wird also "unterbrochen", bis der neuerliche Aufruf von mergeSortCore mit einem Ergebnis zurückkehrt.

Wir befinden uns jetzt in mergeSortCore({40}). Die Länge ist 1 also wird {40} zurückgegeben.

Jetzt sind wir zurück an der der eben unterbrochenen Stelle, die zurückgegebenen {40} werden nun linkeListe zugewiesen und es geht weiter mit der nächsten Zeile:

            rechteListe= mergeSortCore(rechteListe);

Hier passiert wieder das gleiche wie vorhin: mergeSortCore({20}) wird aufgerufen, dabei wird die Ausführung der aktuellen Methode an der aktuellen Stelle unterbrochen. In mergeSortCore({20}) ist die Länge von a 1, also wird {20} zurückgegeben. Die zuvor unterbrochene Methode wird weiter ausgeführt: der Variablen rechteListe wird nun {20} zugewiesen.

Jetzt kommen wir ans Ende der Methode:

            return merge(linkeListe, rechteListe);

D. h. hier wird merge({40},{20}) aufgerufen. Die zwei Arrays sind bereits in sich sortiert. Sie werden zu einem neuen, sortierten Array {20,40} verschmolzen und zurückgegeben. Fertig.

Das ganze nochmal im Schnelldurchlauf für {40,20,30,10}:

mergeSortCore({40,20,30,10})
  Länge > 1 -> teilen {40,20} und {30,10}
  linkeListe=mergeSortCore({40,20})
    // jetzt in mergeSortCore({40,20})
    Länge > 1 -> teilen {40} und {20}
    linkeListe=mergeSortCore({40})
      // jetzt in mergeSortCore({40})
      Länge == 1 -> {40} zurückgeben
    linkeListe={40} zuweisen
    rechteListe=mergeSortCore({20})
      // jetzt in mergeSortCore({20})
      Länge == 1 -> {20} zurückgeben
    rechteListe={20} zuweisen
    merge({40},{20}) = {20,40} zurückgeben
  linkeListe={20,40} zuweisen
  rechteListe=mergeSortCore({30,10})
    // jetzt in mergeSortCore({30,10})
    // wie oben weiter, dann
    merge({30},{10}) = {10,30} zurückgeben
  rechteListe={10,30} zuweisen
  merge({20,40},{10,30}) = {10,20,30,40} zurückgeben.
ENDE

 

[emorej]

.

Danke für deine ausführliche Erklärung, das hat mir wirklich schon gut weitergeholfen. Hänge aber noch bei einem Schritt. Also um zu deinem Beispiel zurückzukommen:

mergeSortCore({40,20,30,10})
  Länge > 1 -> teilen {40,20} und {30,10}
  linkeListe=mergeSortCore({40,20})
    // jetzt in mergeSortCore({40,20})
    Länge > 1 -> teilen {40} und {20}
    linkeListe=mergeSortCore({40})
      // jetzt in mergeSortCore({40})
      Länge == 1 -> {40} zurückgeben
    linkeListe={40} zuweisen
    rechteListe=mergeSortCore({20})
      // jetzt in mergeSortCore({20})
      Länge == 1 -> {20} zurückgeben
    rechteListe={20} zuweisen
    merge({40},{20}) = {20,40} zurückgeben

Bis hierhin ist es jetzt klar für mich. Es wird also {20,40} ausgegeben. Aber bei diesem return müsste die Methode dann ja stoppen, wieso läuft die nach einem return noch weiter?

EDIT. Nochmal Danke für deine Hilfe, habe es jetzt verstanden! Man muss sich erstmal dran gewöhnen, dass die Methode ja mehrmals mit anderen Werten bzw. "Instanzen" läuft. Musste also erst verstehen in mehreren Ebenen zu denken. Trotzdem sind mir Schleifen da aber lieber 😀

MfG