Rekursion Mergesort

Bitte aktiviere JavaScript!
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 ?
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
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?
 
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?
 
Quicksort is schneller. ;)
Es geht ja nicht um das quick sort
Ich muss ein Referat halten um durch meine Abitur Phase zu kommen ich habe diese Chance ich muss jedoch erklären können wie das mergesort sich orientiert und auch beschrieben oder sagen was die rekursion damit zu tun hat und wieso es relevant ist für eine mergesort Programmierung
 
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)
 
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?
?
 
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 ?
 
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...
 
Ein paar Links als Antwort...
Ich verstehe leider nicht so viel englisch
 
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
 
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.
 
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.
 
ach, sie oder du... ich nehme das nicht so genau ;) ... Dafür funktionieren Smilies gerade nich...
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben