Rekursion Mergesort

Jacke

Mitglied
Code:
void sort(int arr[], int links, int rechts)
    {
        if (links < rechts)
        {
   
            int m = (links+rechts)/2;
  
            sort1(arr, links, m);
            sort2(arr , m+1, rechts);
            merge(arr, links, m, rechts);
        }
    }

Ich weiß nicht, ob ich die Rekursion bei Mergesort verstanden habe, deswegen wollte ich einfach mal fragen, ob meine Vorstellung richtig ist.

1: Die Sort1 Methode wird so oft aufgerufen , bis die If-Bedingng nicht mehr stimmt.

2: Der Compiler merkt sich, dass er zuletzt bei sort1 rausgesprungen ist, und beginnt jetzt mit der sort2 Methode, wieder so lange, wie die if-Bedingung true ist.

3: Der Compiler startet jetzt bei der merge methode und arbeitet sich von der letzten Rekursions Ebene nach oben.

Wenn man sich das ganze als Baum vorstellen würde, könnte man doch sagen, dass zuerst der Ast fertig gemacht wird, der ganz links ist, und wenn dann der linke Ast ganz unten ist, wird der nächste gemacht, bis man ganz rechts ist.

Ich hoffe ihr konntet meine Gedankengänge verstehen, und mir sagen, ob ich die Rekursion hier richtig verstanden habe.
 

DrZoidberg

Top Contributor
Wieso denn sort1 und sort2? Du brauchst nur eine sort Methode und die heisst "sort". Übrigens solltest du "links < rechts" abändern in "links < rechts - 1". Denn wenn links gleich rechts - 1 ist, hast du nur ein einziges Element und dann brauchst du auch nichts zu sortieren.
Befehle, die hintereinander stehen, werden auch nacheinander ausgeführt. Sobald sort1 zurückkehrt wird sort2 ausgeführt, danach merge und erst dann kehrt sort zurück.
Du kannst dir das aber schon wie einen Baum vorstellen. Dieser Baum enthält allerdings keine Schleifen.
 

httpdigest

Top Contributor
Alles soweit korrekt. Nur, hat das alles nichts mit dem Compiler zu tun, oder dass er sich da irgendwas "merkt". Die rekursiven Abstiege und Aufstiege entstehen erst zur Laufzeit durch die Callstack Frames der Methodenaufrufe. Die JVM sorgt beim Interpretieren des Codes dafür, dass bei Methodeneintritt entsprechende Stackframes eingefügt werden und beim Beenden einer Methode wieder entfernt werden. Wenn der Code häufig genug ausgeführt wird, und entsprechend von der JVM JIT-compiliert wird, dann findet das Erzeugen der Stackframes durch generierten x86 Code statt und das Betreten und Verlassen von Methoden geschieht dann auch durch x86 call und ret Anweisungen. Das heißt, der Prozessor selbst sorgt dann durch die CPU-Anweisungen dafür, entsprechend Platz auf dem Callstack zu schaffen und beim Verlassen einer Methode wieder zum Aufrufer zurückzuspringen.
 

Jacke

Mitglied
Wenn nach sort aber schon sofort merge kommt, werden die arrays doch niemals vollständig aufgeteilt?
Das heißt bei{3,2,1,6} würde folgendes passieren:
Die Mitte liegt ja bei 1 also eine Aufteilung in:
{3,2} und{1,6}. Wenn ich jetzt im nächsten schritt die Arrays mit merge wieder zusammensetze werden sie doch niemals einelementig.
 

DrZoidberg

Top Contributor
Merge kommt natürlich erst, nachdem sort fertig ist. Und das ist erst dann der Fall, wenn der gesamte "Ast" abgearbeitet wurde. Da es eine rekursive Methode ist, "wandert" der Computer erst bis ganz nach unten ans Ende des Astes und kehrt hinterher wieder zurück. Erst nachdem er wieder am Ausgangspunkt angekommen ist, ist sort fertig.
 

Jacke

Mitglied
Also war meine Vorstellung doch richtig, dass erst die beiden Sort Methoden abgearbeitet werden und dann die Merge-Methode?
 

DrZoidberg

Top Contributor
Ja. Es werden erst die sort Methoden aufgerufen und hinterher merge.
Aber du hattest behauptet, dass zuerst sort1 solange aufgerufen wird, bis die If Bedingung nicht mehr stimmt und danach dann sort2 so lange bis die Bedingung nicht mehr stimmt. Und diese Aussage ist so einfach falsch.

Eine Möglichkeit sich das ganze vorzustellen ist sich zu fragen, was passiert, wenn eine Gruppe von Personen den Code manuell ausführt, anstatt das von einem Computer erledigen zu lassen.
Diese Personen erhalten alle ein Buch, in dem sämtliche Methoden des Programms drin stehen. Mal angenommen Person1 erhält einen Zettel, mit der Anweisung "sort({3,2,1,6}, 0, 3)". Dann schlägt sie zuerst die Methode sort im Buch nach und fängt dann an die Anweisungen nacheinander auszuführen. Zuerst "if(links < rechts)". Da die Bedingung wahr ist, führt sie nun die Anweisungen innerhalb der Klammern {} aus. Das wäre dann erst "int m = (links+rechts)/2;" und danach dann "sort(arr, links, m);". Dann schreibt Person1 die Anweisung "sort({3,2,1,6}, 0, 1)" auf einen Zettel und gibt den an Person2, die das Ganze dann abarbeitet. Person1 wartet so lange, bis sie die Antwort von Person2 erhalten hat und macht danach erst mit der nächsten Zeile weiter.
 

Jacke

Mitglied
Ok das verstehe ich. Der nächste Schritt wäre dann ja sort({3,2,1,6},0,0) Das würde dann ja nicht gehen, wie geht es dann weiter?
 

DrZoidberg

Top Contributor
Nun bei "sort({3,2,1,6},0,0)" ist die if Bedingung nicht mehr erfüllt. Person3 führt die Anweisungen, die nach dem if kommen also nicht aus und teilt dann Person2 mit, dass sie fertig ist. Person2 kann nun weitermachen und die restlichen Anweisungen ausführen. Sobald sie mit allem fertig ist, meldet sie sich bei Person1 die dann ihrerseits fortfahren kann. Anders gesagt - sobald man ganz unten am Ende des Astes angelangt ist, steigt man wieder hinauf, bis man irgendwann auf der obersten Ebene des Baumes (bei Person1) angekommen ist.
 

Jacke

Mitglied
Als Ansatz in etwa also so:

sort({3,2,1,6},0,3)= sort({3,2,1,6},0,1)= sort({3,2,1,6},0,0)//geht nicht also jetzt sort von m bis r.
sort({3,2,1,6},0,1}= sort({1,0})// geht auch wieder nicht. Also jetzt wird merge aufgerufen.
merge({3,2,1,6},0,1}=merge({3,2,1,6},0,3). Dann wäre ich wieder ganz oben und würde mich genauso von sort({3,2,1,6},2,3) runterarbeiten.

Stimmt der Ansatz so?
 

DrZoidberg

Top Contributor
Deine Zahlen stimmen nicht ganz.
Ich hab mal versucht das tabellarisch hinzuschreiben. Die 3. Ebene hab ich weg gelassen, da dort die If Bedingung nicht mehr erfüllt ist und daher dort auch nichts mehr passiert, zumindest nicht in der sort Methode.
Code:
main Methode         | sort (1. Ebene)        |  sort (2. Ebene)

sort({3,2,1,6},0,3) -> sort({3,2,1,6},0,1)    -> sort({3,2,1,6},0,0)
                                                 sort({3,2,1,6},1,1)
                                                 merge({3,2,1,6},0,0,1)
                       sort({2,3,1,6},2,3)    -> sort({2,3,1,6},2,2)
                                                 sort({2,3,1,6},3,3)
                                                 merge({2,3,1,6},2,2,3)
                       merge({2,3,1,6},0,1,3)
Der letzte Aufruf von merge fügt dann übrigens die beiden Listen {2,3} und {1,6} zur Liste {1,2,3,6} zusammen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
P Rekursion Aufrufbaum Allgemeine Java-Themen 7
N rekursion mehrfach eine Methode Öffnen Allgemeine Java-Themen 4
districon Rekursion und Dynamische Programmierung Allgemeine Java-Themen 2
Zeppi Rekursion StackOverflowError Allgemeine Java-Themen 4
J Rekursion Allgemeine Java-Themen 4
Zrebna Wie kann man endgültig aus einer Rekursion ausbrechen? Allgemeine Java-Themen 14
parrot Rekursion Aufgabe Allgemeine Java-Themen 12
B Rekursion Allgemeine Java-Themen 11
X Wie mache ich hier eine Rekursion rein ? Allgemeine Java-Themen 7
R Rekursion Allgemeine Java-Themen 3
R Programm zur Rekursion Allgemeine Java-Themen 5
V Rekursion Allgemeine Java-Themen 2
J Denkfehler Rekursion Allgemeine Java-Themen 5
I Raute mit Rekursion "zeichnen" Allgemeine Java-Themen 7
B Rekursion Allgemeine Java-Themen 2
B Rekursion Allgemeine Java-Themen 22
B Java Sternchen ausgeben mittels Rekursion Allgemeine Java-Themen 3
Hacer Rekursion- sumOfAllNodes Allgemeine Java-Themen 5
L Rekursion Binärbaum Allgemeine Java-Themen 7
Androbin Interpreter-Fehler Probleme mit Rekursion - StackOverflowError Allgemeine Java-Themen 8
Y Rekursion Allgemeine Java-Themen 19
M Permutation ohne Wiederholung mit rekursion Allgemeine Java-Themen 4
J Rekursion oder Iteration - verkettete Listen Allgemeine Java-Themen 8
T Pascalsches Dreieck ohne array und rekursion Allgemeine Java-Themen 9
P Rekursion Allgemeine Java-Themen 9
R Threading und Rekursion führen zu “GC overhead limit exceeded” Allgemeine Java-Themen 4
W Rekursion-Probleme mit return Allgemeine Java-Themen 35
C Rekursion Fibonacci Allgemeine Java-Themen 31
T Rekursion mit While Schleife kombinieren? Allgemeine Java-Themen 4
eQuest Rekursion Dauer Allgemeine Java-Themen 6
Weiti Swingworker und Rekursion Allgemeine Java-Themen 8
L fragwürdige Rekursion Allgemeine Java-Themen 4
L Kleine Rekursion Allgemeine Java-Themen 12
M Rekursion!! Allgemeine Java-Themen 8
J Rekursion in Schleifenkonstrukt wandeln Allgemeine Java-Themen 21
R Rekursion Ablauflogik Allgemeine Java-Themen 19
M Rückwärts geführte Rekursion Allgemeine Java-Themen 3
Schandro StackOverflowError bei Rekursion verhindern Allgemeine Java-Themen 14
G Werte bei Rekursion viel höher als erwartet Allgemeine Java-Themen 3
G Rekursion - Denksport Allgemeine Java-Themen 6
S Rekursion und StackOverflow Allgemeine Java-Themen 11
P Stackoverflow in Rekursion. Bin ich schuld oder Java? Allgemeine Java-Themen 9
W kompliziertes Konstrukt von Schleifen/If/else. Rekursion? Allgemeine Java-Themen 22
S Rekursion Allgemeine Java-Themen 2
Linad Tiefe der Rekursion als Abbruchbedingung Allgemeine Java-Themen 6
Linad Zahlensysteme -> Rekursion Allgemeine Java-Themen 4
N Frage zu einer Rekursion Allgemeine Java-Themen 4
Devin Mergesort verstehen Allgemeine Java-Themen 3
Kirby.exe K-Way MergeSort Allgemeine Java-Themen 33
L MergeSort allgemein Allgemeine Java-Themen 61
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
X MergeSort Laufzeit Problem Allgemeine Java-Themen 4
T Threads Mergesort mit limitierter Threadanzahl Allgemeine Java-Themen 2
S MergeSort iterativ und rekursiv? Allgemeine Java-Themen 8
B Generische Datentypen MergeSort Allgemeine Java-Themen 5
B Hilfe beim Verständnis von Mergesort Allgemeine Java-Themen 5
R MergeSort funktioniert nicht Allgemeine Java-Themen 5
D MergeSort Allgemeine Java-Themen 19
H [LinkedList] Sortieren durch MergeSort Allgemeine Java-Themen 3
N externes Sortieren (MergeSort Allgemeine Java-Themen 2

Ähnliche Java Themen

Neue Themen


Oben