MergeSort

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

MergeSort

Beitrag von null »

Hallo zusammen,Ich sehe das aber anders und da bitte euch, meinen wahrscheinlichen Denkfehler zu finden

ich hatte den MergeSort bereits in der Schule kennengelernt, doch heute in der Vorlesung war ich von der Erklärung etwas überrascht und habe dazu noch eine Frage. Professor Weihe hat mehrmals darauf hingwiesen, dass laut der Schleifenvariante nach einem Rekursionsschritt die aktuelle Sequenz sortiert ist. Ich zitiere dazu mal aus der Wiki:

"The sequence of the current recursive call is sorted."

Ich stelle mir das aber anders vor und bin mit obigen Statement (noch) nicht einverstanden. Pro rekursiven Aufruf wird die Sequenz durch zwei geteilt, sodass nach log_{2}(n) - Schritten alle Daten atomar vorliegen. Beispiel

4321
43 21
4 3 2 1

Jedoch wird hier noch nichts sortiert. Der Sortiervorgang fängt ja eigentlich erst beim Zusammenfügen, also bei "merge" an, genau dann, wenn die Sequenz ganz aufgeteilt wurde. Es würde also so weitergehen:

34 12
1234

Obwohl oben drei rekursive Aufrufe gemacht wurden, ist nichts sortiert. Wie habe ich also die Schleifeninvariante zu verstehen, denn so macht sie für mich (noch) keinen Sinn.

Herzlichen Dank

mcdikki
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 22. Okt 2007 17:16
Wohnort: Frankfurt

Re: MergeSort

Beitrag von mcdikki »

Naja,

nach jeder rekursion habe ich merge schon auf den beiden teilsequenzen ausgeführt.

Also:

4321
rufe ms auf
43 21
rufe ms auf
4 3 2 1
Habe anker und rufe ms nicht mehr auf!

So jetzt geht es zurück:

-> Ist sortiert, mache nichts (anker halt ;-) )
4 3 2 1
alle 4 teilseq sind sortiert.
merge 3&4 und 1&2 (vorsicht, dann sind verschieden stellen der rek, nur auf der gleichen ebene)
34 12
alle beiden teilseq sind sortiert
merge 34 & 12
1234
die (teil)seq. ist sortiert

Fertig.

Du siehst also, beim rückschritt sind nach jeder rekursion die teilsequenzen sortiert.
Das kann durch den aufruf durch merge passiert sein, muss aber nicht (anker).
Du musst jetzt aber noch die beiden Teilsequenzen mergen.
Erst jetzt hast du alle befehle die in der Invariante vorkommen abgearbeitet und sie ist erfüllt.

hoffe das war verständlich.

lg mcdikki

mcdikki
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 22. Okt 2007 17:16
Wohnort: Frankfurt

Re: MergeSort

Beitrag von mcdikki »

Nachtrag:

Außerdem sagt die Invariante ja nur aus, was nach einem Schritt für eine Situation garantiert wird, nicht unbedingt wie man sie erreicht. Das steht im Wiki dann im Abstract view vom Induktionsschritt

lg mcdikki

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

mcdikki hat geschrieben:Du siehst also, beim rückschritt sind nach jeder rekursion die teilsequenzen sortiert.
Hallo,

ich verstehe deine Argumentation. Da pro Rekursionsschritt "merge" aufgerufen wird, kann ich die aktuelle Sequenz als sortiert ansehen. Es hakt bei mir aber noch an einer Stelle:

Ich habe jetzt eine lange Liste. Jetzt teile ich sie zum ersten Mal und rufe merge auf. Jetzt sortiert merge diese beiden großen Teillisten und....eigentlich fertig! Warum dann noch die ganzen Selbstaufrufe des mergeSorts?

Auch das schöne Buchstabenbeispiel macht einem klar, dass erst aufgeteilt wird und dann sortiert wird.

Vielleicht bin ich auch einfach durch die Rekursionsstufen verwirrt.

Vielen Dank für deine lange Erklärung

mcdikki
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 22. Okt 2007 17:16
Wohnort: Frankfurt

Re: MergeSort

Beitrag von mcdikki »

null hat geschrieben: Ich habe jetzt eine lange Liste. Jetzt teile ich sie zum ersten Mal und rufe merge auf. Jetzt sortiert merge diese beiden großen Teillisten und....eigentlich fertig! Warum dann noch die ganzen Selbstaufrufe des mergeSorts?
Ganz einfach, weil wir mit dem Merge Algo keine sortierte Sequenz erhalten würden. Hier mal ein Beispiel:

463215
die Teilen wir jetzt einfach in der Mitte:
463 215
und jetzt Merge:
(2<4, 1<6, 3<5)
241635

Diese Sequenz ist leider nicht sortiert.Dafür müssen die beiden Teilsequenzen die an Merge gehen schon sortiert sein.
Ich habe die Seite im Wiki vorhin schon dementsprechend angepasst.

Deshalb ist es auch enorm wichtig, dass wir zuerst die liste aufteilen (also bis in ihre Atome) und dann merge aufrufen.

Hoffe damit ist der Sinn der Aufteilung der Sequenz in atomare Teile klar geworden.
Prinzip ist wie immer bei Teile&Herrsche. Es ist einfacher ein großes Problem in viele kleine Probleme zu teilen und zu lösen (Sortiere kein oder 1 Element richtig) und es
dann wieder zusammen zu setzten (Merge, ist sehr einfach).

lg mcdikki

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

Hallo :D

Danke für deine Antwort. Gut, ich zerlege also die ganze Liste in ihre Atome. Das habe ich soweit verstanden. Meiner Ansicht nach kann aber die Teilsequenz des aktuellen rekursiven Aufrufs dann aber noch nicht sortiert sein. Ich muss sie ja erstmal teilen (das sind schon ein paar rekursive Aufrufe) und erst danach beginnt mit "merge" die eigentliche Sortierung.

Angenommen ich habe jetzt die folgende Liste atomar zerlegt:

5 4 3 2 1 0

Nun schaue ich in die Wiki, um mir den Merge-Algorithmus näher anzuschauen. So wie das verstehe, habe ich jetzt quasi sechs Teillisten mit der Länge 1. Ich möchte jetzt zuerst die beiden Teillisten, die 5 und 4 enthalten, zusammenfügen. Also habe ich laut Wiki i1 = 0 und i2 = 0. Jetzt möchte ich wissen, welcher der fünf in der Wiki unter "Inductionstep" genannten Schritte zutrifft:

1.) Trifft nicht zu, da i1 != 1 und i2 !=2
2.) Trifft nicht zu, da i1 != 1
3.) Trifft nicht zu, da i2 != 1
4.) Trifft nicht zu, da S1[i1+1] nicht definiert ist. Wenn die Liste atomar vorliegt, hat S1 ja nur ein Element.
5.) Feher, da S2[i2+1] nicht definiert ist. Wenn die Liste atomar vorliegt, hat S2 ja nur ein Element.

Irgendwie würde bei mir "Merge" nicht funktionieren. Wo liegt also der Fehler? Über Hilfe wäre ich sehr dankbar!

Herzlichen Dank

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: ...

Also habe ich laut Wiki i1 = 0 und i2 = 0.
...

5.) Feher, da S2[i2+1] nicht definiert ist. Wenn die Liste atomar vorliegt, hat S2 ja nur ein Element.
In diesem Fall ist i2+1=1, und im Wiki fangen Listen (im Gegensatz zu Java) immer mit Position 1 an, also kein Fehler, oder?

Ich bin mir nicht sicher, ob diese "atomare" Sichtweise wirklich für's Verständnis hilft oder nicht sogar irreführend sein kann. Denken Sie daran, dass Sie zwar (5) mit (4) mergen, aber nicht (3) mit (2), sondern Sie mergen dann irgendwann (4,5) mit (3) zu (3,4,5) und genauso (1,2) mit (0) zu (0,1,2), und schließlich (3,4,5) und (0,1,2) zu (0,1,2,3,4,5).

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

Prof. Karsten Weihe hat geschrieben: In diesem Fall ist i2+1=1, und im Wiki fangen Listen (im Gegensatz zu Java) immer mit Position 1 an, also kein Fehler, oder?
Gut, wenn Strings generell bei 1 anfangen, dann macht es Sinn.
Prof. Karsten Weihe hat geschrieben: Ich bin mir nicht sicher, ob diese "atomare" Sichtweise wirklich für's Verständnis hilft oder nicht sogar irreführend sein kann. Denken Sie daran, dass Sie zwar (5) mit (4) mergen, aber nicht (3) mit (2), sondern Sie mergen dann irgendwann (4,5) mit (3) zu (3,4,5) und genauso (1,2) mit (0) zu (0,1,2), und schließlich (3,4,5) und (0,1,2) zu (0,1,2,3,4,5).

KW
Da verstehe ich Wikipedia aber anders. Wenn ich mir das gegebene Beispiel mit den Buchstaben anschaue, das vom Aufbau mit meinem identisch ist, dann würde zuerst 5 mit 4, 3 mit 2 und 1 mit 10 gemergt. Es entsünde der folgende Baum

5 4 3 2 1 0
45 23 10
2334 10
012345

Hier ist das Beispiel: http://de.wikipedia.org/wiki/Mergesort#Beispiel

Hier sind zwar keine Zahlen vorhanden, sondern Buchstaben, doch verändet sich dadruch ja nichts. Sobald der "Mischen" - Schritt anfängt werden zuerst "a n" und "e x", respektive "5 4" und "2 3" gemergt.

Verstehe ich Sie falsch oder ist das Beispiel in Wikipedia falsch oder wo ist der Fehler? :)
Danke

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: Gut, wenn Strings generell bei 1 anfangen, dann macht es Sinn.
Nein, Sequences im Sinne des Wikis fangen mit Position 1 an, siehe Wiki-Seite "Sets and sequences".

null hat geschrieben: Da verstehe ich Wikipedia aber anders.
Wenn ich das Beispiel (5,4,3,2,1,0) streng nach Logik in Wikipedia bearbeite, dann wird zerlegt:

(5,4,3,2,1,0) in (5,4,3) und (2,1,0),
(5,4,3) in (5) und (4,3) // da bei ungerader Anzahl offenbar immer die zweite Teilsequenz 1 mehr bekommt
(2,1,0) in (2) und (1,0)
(4,3) in (4) und (3)
(1,0) in (1) und (0)

Beim Merge geht es dann in jeder Zeile von rechts nach links.

null hat geschrieben: Wenn ich mir das gegebene Beispiel mit den Buchstaben anschaue, das vom Aufbau mit meinem identisch ist, dann würde zuerst 5 mit 4, 3 mit 2 und 1 mit 10 gemergt.
Wie das :?: :shock:

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

Prof. Karsten Weihe hat geschrieben:
Wenn ich das Beispiel (5,4,3,2,1,0) streng nach Logik in Wikipedia bearbeite, dann wird zerlegt:

(5,4,3,2,1,0) in (5,4,3) und (2,1,0),
(5,4,3) in (5) und (4,3) // da bei ungerader Anzahl offenbar immer die zweite Teilsequenz 1 mehr bekommt
(2,1,0) in (2) und (1,0)
(4,3) in (4) und (3)
(1,0) in (1) und (0)
Richtig, so verstehe ich Wikipedia auch: Erst wird alles zerlegt und dann wird es zusammengefügt.
Prof. Karsten Weihe hat geschrieben:
null hat geschrieben: Wenn ich mir das gegebene Beispiel mit den Buchstaben anschaue, das vom Aufbau mit meinem identisch ist, dann würde zuerst 5 mit 4, 3 mit 2 und 1 mit 10 gemergt.
Wie das :?: :shock:

KW
Ich meine die Stelle, an der der Mergeteil beginnt, also wo die grünen Pfeile beginnen. Erst werden "a n" gemergt, dann "e x", dann "a m" usw. Das ist aber gleichbedeutend mit meinem gebrachten Beispiel, denn erste merge ich "5 4", dann "3 2" und dann "1 0". Sie sagen aber, das ich nicht 3 mit 2, sondern "45)" mit 3 merge. Kann ich daraus schließen, dass Wikipedia falsch liegt oder die Zeichnung mindestens falsch verstehe?

Danke

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: Ich meine die Stelle, an der der Mergeteil beginnt, also wo die grünen Pfeile beginnen. Erst werden "a n" gemergt, dann "e x", dann "a m" usw. Das ist aber gleichbedeutend mit meinem gebrachten Beispiel
Ich denke, diese Korrespondenz ist reiner Zufall :!: :shock:

Entscheidend ist, dass die Merge-Operationen spiegelsymmetrisch genau die Struktur der Zerlegungsoperationen hat: Wenn S in S1 und S2 zerlegt wird, dann (und nur dann) werden S1 und S2 zu S gemergt. Das ist im Beispiel ebenfalls gut zu sehen. Da 3 und 2 schon auf der obersten Stufe getrennt werden, kommen sie auch erst auf der obersten Stufe wieder zusammen, nämlich beim Merge von (3,4,5) und (0,1,2).

KW

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

Prof. Karsten Weihe hat geschrieben: Entscheidend ist, dass die Merge-Operationen spiegelsymmetrisch genau die Struktur der Zerlegungsoperationen hat: Wenn S in S1 und S2 zerlegt wird, dann (und nur dann) werden S1 und S2 zu S gemergt. Das ist im Beispiel ebenfalls gut zu sehen. Da 3 und 2 schon auf der obersten Stufe getrennt werden, kommen sie auch erst auf der obersten Stufe wieder zusammen, nämlich beim Merge von (3,4,5) und (0,1,2).

KW

Danke, ich komme der Lösung meines Gehirnsalats immer näher :D Ich muss dennoch noch einmal nachhaken:
Prof. Karsten Weihe hat geschrieben:
null hat geschrieben: Ich meine die Stelle, an der der Mergeteil beginnt, also wo die grünen Pfeile beginnen. Erst werden "a n" gemergt, dann "e x", dann "a m" usw. Das ist aber gleichbedeutend mit meinem gebrachten Beispiel
Ich denke, diese Korrespondenz ist reiner Zufall :!: :shock:
Ich denke hier an keinen Zufall, sondern vermute, dass entweder Zwischenschritte ausgelassen wurden oder das Grundverständnis anders ist. So wie ich Sie verstehe, muss beim Beispiel von Wikipedia erst "a n" gemergt werden, bevor "ex" überhaupt geteilt wird. Falls das der Fall ist, dann würde auch meine Ausgangsfrage zur Aussage "The sequence of the current recursive call is sorted" endlich eine befriedigende Antwort erhalten. Meine These wird übrigens auch von diesem Video bestätigt:

http://www.youtube.com/watch?v=XaqR3G_NVoo

Können Sie mich also damit bestätigen: "Bevor "ex" überhaupt geteilt wird, ist "an" bereits geteilt und gemergt worden". Das würde aber bedeuten, dass Zeichnung von Wikipedia sehr missverständlich ist, da dort erst alles geteilt wird und danach der Merge-Vorgang eintritt.

Herzlichen Dank für die tolle Hilfe!!

PS.: Solch ein Video wäre doch super für eine der nächsten Pausen :mrgreen:

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort

Beitrag von JannikV »

Bin zwar nicht der Professor, aber ich sage dennoch mal dazu was ich denke:

Das kommt ja auf die Implementierung an. Wenn eine MergeSort Instanz hintereinander zwei rekursive Aufrufe macht, dann müsste das so sein wie du es gesagt hast. Dann wird die Rekursion erst eine Seite bis "ganz nach unten" gegangen und gemerged. Und dann erst wird der zweite Aufruf überhaupt ausgeführt.

Interessant wäre vielleicht, wenn man das in Zeiten von Multicoreprozessoren über parallele Threads lösen würde. ^^


VG

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: MergeSort

Beitrag von null »

Das würde dann aber bedeuten, dass der Pseudocode in Wikipedia nicht mit der Abbildung übereinstimmt. Ich zitiere mal:

funktion mergesort(liste);
falls (Größe von liste <= 1) dann antworte liste
sonst
halbiere die liste in linkeListe, rechteListe
linkeListe = mergesort(linkeListe)
rechteListe = mergesort(rechteListe)
antworte merge(linkeListe, rechteListe)


Dieser Code spricht für meine Hypothese, also dass die Rekursion erst ganz links bis nach ganz unten geht und dann gemergt geht, bzw. dass erst "an" getrennt und gemergt werden, bevor "ex" überhaupt angerührt wird....

Danke

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort

Beitrag von JannikV »

Ja, das läuft sequenziell ab. Ich denke die Abbildung will einfach nur durch den kompletten Rekursionsbaum klarmachen wie der Algorithmus funktioniert. Das geschieht nicht alles gleichzeitig, jedenfalls nicht mit der Implementierung.

VG

Antworten

Zurück zu „Archiv“