Rekursion Mergesort

Osbscsusb

Mitglied
Hey Leute wenn wir schon dabei sind hätte ich auch ganz kurz eine Frage . Und zwar habe ich fragen bei denen ich eine Antwort brauche . Das Prinzip von Mergesort habe ich verstanden jedoch verstehe ich nicht wofür oder für was ein mergesort Programm ein rekursion benötigt und was genau hat rekursion mit mergesort zu tun .

Mir ist ja bewusst das wenn man ein Array hat wie zum Beispiel
3 6 8 5 7 9 2 1
Man das zerteilen muss entspricht so dass man zwei unsortierte arrays hat
3 6 8 5 7 9 2 1
Und die muss man noch mal zerlegen bis man die alle Einzel stehen hat
36 85 79 21
Diese wiederum nochmal zerlegen
3 6 8 5 / 7 9 2 1
Diese sind jetzt sortiert und Diese muss man dann so zu sagen vermischen
Das heißt :
Da die 3 kleiner ist als die 6 wird
36 beibehalten
36 aber da die 5 kleiner ist als die 8 werden die vertauscht entspricht
36 58
Genau so gehts bei der 7 und 9 . Da die 7 kleiner ist als die 9 kann man das beibehalten
79 aber da die 1 kleiner ist als die zwei wird’s vertauscht
Heißt 12
Dann hat man das vor sich liegen
36 58 79 21
Dann schau man sich an ob die 3 größer ist als die 5 in dem Fall ist es größer
Deshalb schreibt man sich die 3 auf
3 dann schaut man sich an ob die 6 größer als die 5 ist in dem Fall nicht heißt man schreibt sich nun die 5 auch neben der drei auf
35 dann schaut man sich ob die 6 kleiner ist als die 8 was in dem Fall so ist heißt
Jetzt haben wir ein sortiertes halbes Array
3568 und machen das gleiche mit dem anderen halben Array auch
2 ist kleiner als 7 heißt schreiben die 2 auf
7 ist größer als 1 heißt schreiben die 1 auf
7 ist größer als 9 heißt schreiben die 7 auf
2179
3568 2179

Jetzt das gleiche Prinzip
Die 2 ist kleiner als die 3
Also wird sie aufgeschrieben
21356789

Was hat rekursiv damit aber zu tun und für was benötigt man das ?
 

httpdigest

Top Contributor
Der Algorithmus, den du gerade exemplarisch durchgespielt hast, ist genau der rekursive top-down Algorithmus für Merge Sort. Du sagst am Anfang, man muss das Array immer weiter zerteilen, bis man quasi einelementige Arrays hat. Und dann muss man immer jeweils zwei (bereits sortierte) Arrays zusammen mergen, bis man wieder ein einzelnes zusammenhängendes, sortiertes Array hat.
Genau das ist top-down rekursive Merge Sort. Der rekursive "Abstieg" (das Zerteilen eines Arrays in zwei Teilarrays) sowie der rekursive "Aufstieg" (das Mergen der zwei sortierten Teilarrays) ist ja ein immer wiederkehrender Prozess, der für jede Zerteilung des Arrays immer gleich aussieht. Somit kann man Merge Sort sehr elegant und kurz mittels Rekursion implementieren.

Oder anders gefragt: Was glaubst du denn, was Rekursion ist? Was stellst du dir darunter vor?
 

Osbscsusb

Mitglied
Der Algorithmus, den du gerade exemplarisch durchgespielt hast, ist genau der rekursive top-down Algorithmus für Merge Sort. Du sagst am Anfang, man muss das Array immer weiter zerteilen, bis man quasi einelementige Arrays hat. Und dann muss man immer jeweils zwei (bereits sortierte) Arrays zusammen mergen, bis man wieder ein einzelnes zusammenhängendes, sortiertes Array hat.
Genau das ist top-down rekursive Merge Sort. Der rekursive "Abstieg" (das Zerteilen eines Arrays in zwei Teilarrays) sowie der rekursive "Aufstieg" (das Mergen der zwei sortierten Teilarrays) ist ja ein immer wiederkehrender Prozess, der für jede Zerteilung des Arrays immer gleich aussieht. Somit kann man Merge Sort sehr elegant und kurz mittels Rekursion implementieren.

Oder anders gefragt: Was glaubst du denn, was Rekursion ist? Was stellst du dir darunter vor?

Achso also heißt es das dieser Vorgang den ich beschrieben habe der rekursive Vorgang ist ? Also kann ich auf die Frage warum man eine rekursion für eine mergesort Programmierung brauche damit antworten , dass sich das Array immer weiter zerteilt bis es sich zu einem sortieren Array bildet ?
Ist das was ich beschrieben habe praktisch ein rekursionsauffbau?
 
X

Xyz1

Gast
Die Rekursion ist der divide & conquer -Schritt... bla bla... im Divide-Schritt teilen wir das Array auf in kleinere Arrays auf... bla bla... im Conquer-Schritt fügen wir kleinste Arrays wieder planvoll zusammen... bla bla.
Und das eben noch eingebettet in Problemstellung, Ausgangssituation, Fragestellung, Beschreibung, Fazit, Ausblick. (Wobei 1,3,5 entfallen kann)
 

Osbscsusb

Mitglied
Der Algorithmus, den du gerade exemplarisch durchgespielt hast, ist genau der rekursive top-down Algorithmus für Merge Sort. Du sagst am Anfang, man muss das Array immer weiter zerteilen, bis man quasi einelementige Arrays hat. Und dann muss man immer jeweils zwei (bereits sortierte) Arrays zusammen mergen, bis man wieder ein einzelnes zusammenhängendes, sortiertes Array hat.
Genau das ist top-down rekursive Merge Sort. Der rekursive "Abstieg" (das Zerteilen eines Arrays in zwei Teilarrays) sowie der rekursive "Aufstieg" (das Mergen der zwei sortierten Teilarrays) ist ja ein immer wiederkehrender Prozess, der für jede Zerteilung des Arrays immer gleich aussieht. Somit kann man Merge Sort sehr elegant und kurz mittels Rekursion implementieren.

Oder anders gefragt: Was glaubst du denn, was Rekursion ist? Was stellst du dir darunter vor?
?
 

Osbscsusb

Mitglied
Die Rekursion ist der divide & conquer -Schritt... bla bla... im Divide-Schritt teilen wir das Array auf in kleinere Arrays auf... bla bla... im Conquer-Schritt fügen wir kleinste Arrays wieder planvoll zusammen... bla bla.
Und das eben noch eingebettet in Problemstellung, Ausgangssituation, Fragestellung, Beschreibung, Fazit, Ausblick. (Wobei 1,3,5 entfallen kann)
Also meinen sie damit das die rekursion aus einem divide und conquer schritt besteht ?
Wobei der divide zerteilt und der conquer Schritt sie wieder zusammen fügt ? Das ist die rekursion ? Und wieso ist er relevant in der mergeprogrammierung ?
 
X

Xyz1

Gast
Also meinen sie damit das die rekursion aus einem divide und conquer schritt besteht ?
Wobei der divide zerteilt und der conquer Schritt sie wieder zusammen fügt ? Das ist die rekursion ? Und wieso ist er relevant in der mergeprogrammierung ?
Ein paar Links als Antwort...
 

Osbscsusb

Mitglied
Ein paar Links als Antwort...
Ich verstehe leider nicht so viel englisch
 

Osbscsusb

Mitglied
Mir fällt da irgendwie der Spruch ein: "I can explain it to you, but I cannot understand it for you."
Hmm okay dann soll es wohl so sein dann bedanke ich mich Trz bei dir . Das Ding ist ich muss mich selbst über das Thema schlau . Es ist neu und ich hatte keinen der sich schon damit auskannte . Also schreib ich praktisch ein Referat über ein Thema was ich mir selbst im Internet erklären soll . Und bei fragen darf ich mich nicht an die Lehrkraft wenden da sie mir die nicht beantworten wird weil es eine Recherche Aufgabe ist
 

httpdigest

Top Contributor
Das ist schonmal exakt genau die richtige Einstellung für ein Studium. Nur, dass Professoren dir Fragen nicht beantworten, weil sie nicht dürfen, sondern weil sie keine Zeit haben. Aber ansonsten ist das genau die richtige Beschreibung für ein Studium.
 

mihe7

Top Contributor
Also meinen sie damit das die rekursion aus einem divide und conquer schritt besteht ?
Wobei der divide zerteilt und der conquer Schritt sie wieder zusammen fügt ? Das ist die rekursion ? Und wieso ist er relevant in der mergeprogrammierung ?
Also, erstens sind wir hier per Du.

Zweitens: Rekursion bedeutet einfach nur, dass eine Funktion unter Rückgriff auf eben diese Funktion berechnet wird. Die Fakultät lässt sich z. B. rekursiv definieren als:
Code:
f(0) = 1
f(n) = f(n-1)*n (für alle n > 0)

Bei der Berechnung lässt sich zwischen dem rekursiven Ab- und Aufstieg unterscheiden. Willst Du z. B. f(4) berechnen, musst Du erstmal absteigen, also
Code:
f(4) = f(3) * 4
f(3) = f(2) * 3
f(2) = f(1) * 2
f(1) = f(0) * 1
f(0) = 1
um dann aufsteigen und das Ergebnis berechnen zu können:
Code:
f(0) = 1
f(1) = f(0) * 1 = 1 * 1 = 1
f(2) = f(1) * 2 = 1 * 2 = 2
f(3) = f(2) * 3 = 2 * 3 = 6
f(4) = f(3) * 4 = 6 * 4 = 24

Mergesort funktioniert nach dem Prinzip "teile und herrsche": das Ausgangsproblem ist zu groß, also wird es so lange in kleinere Probleme zerteilt (teile-Phase), bis diese leicht lösbar sind und zu einer Gesamtlösung zusammengeführt werden können (herrsche-Phase). Das Prinzip hat an sich noch nichts mit Rekursion zu tun.

Zur Umsetzung dieses Prinzips wendet Mergesort jedoch Rekursion an: beim Abstieg wird das Problem geteilt (der Abstieg erfolgt so lange, bis das Problem trivial ist), beim Aufstieg wird die Lösung berechnet.

Und jetzt kannst Du Dir mal überlegen, warum Mergesort funktioniert.
 
X

Xyz1

Gast
ach, sie oder du... ich nehme das nicht so genau ;) ... Dafür funktionieren Smilies gerade nich...
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Rekursion (anhand von Mergesort) nachvollziehen Java Basics - Anfänger-Themen 4
B mergesort/rekursion Java Basics - Anfänger-Themen 9
K Verstehe Rekursion nicht ganz Java Basics - Anfänger-Themen 7
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
DiyarcanZeren Rekursion in Java Java Basics - Anfänger-Themen 5
M Variablen Rekursion mit 2 Parameteren Java Basics - Anfänger-Themen 4
sserio Rekursion größten Primfaktor finden funktioniert nicht Java Basics - Anfänger-Themen 8
M Lösungsweg Rekursion Java Basics - Anfänger-Themen 1
C StackOverflow bei Rekursion Java Basics - Anfänger-Themen 7
D Rekursion - Ich raffs nicht Java Basics - Anfänger-Themen 16
N Methoden Rekursion mit Kreisen Java Basics - Anfänger-Themen 7
P9cman Vokale in einem String überprüfen mittels Rekursion Java Basics - Anfänger-Themen 8
J Rekursion Java Basics - Anfänger-Themen 22
T Rekursion Programmierverständnis Java Basics - Anfänger-Themen 12
K Rekursion: Rechenmauer mit Array erstellen Java Basics - Anfänger-Themen 17
K Rekursion einer Zahlenfolge (Ab- und Aufzählung) Java Basics - Anfänger-Themen 6
Zeppi Rekursion Java Basics - Anfänger-Themen 15
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 9
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
G rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben