Mergesort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | wir haben folgende Liste von Zahlen L1={8,4,5,1,2,7,3,6}
Nun sollen wir ermittlen wieviel vergleichoperationen nötig sind, um diese Liste nach dem mergesort-Algorithmus zu sortieren. |
Nun meine Frage:
Beim Mergesort-Algorithmus wird die Liste so lange durch 2 geteilt, bis die lemente einzeln sind und dann miteinander verglichen und dann wieder vermischt und verglichen usw.
Nun komme ich bei dieser Liste auf 44 vergleichoperationen.
Ist das korrekt?
Wenn nicht könntet ihr mir schildern, wie ich da am besten vor gehe?
Gruß niesel
|
|
| |
|
Hallo,
also 44 erscheint mir doch arg hoch. Überleg doch mal, wie der Algorithmus funktioniert. Du hast insgesamt [mm] $\log [/mm] 8$ tiefen Berechnungsbaum. In der ersten Ebene hast Du 4 mal 2 einelementige Listen, für die Du jeweils eine Vergleichsoperation braucht. Wieviel Vergleichoperationen brauchst Du denn für das Mischen von 2 2-elementigen Listen oder 2 4-elementigen Listen?
Du solltest auf 12 Vergleichsoperationen kommen, wenn ich mich jetzt nicht verrechnet habe. Beachte, dass Du bei dem Mischen zwei sortierte Listen hast, dadurch ist ja gerade der Algorithmus so schick... Teile und Herrsche! 
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:39 Mo 01.05.2006 | | Autor: | kretschmer |
Hallo,
ohja müssten 17 sein. Hatte jeweils einen unterschlagen beim Mischen von zweielementigen Listen und drei weitere beim Schritt danach. Hmm frage mich auch gerade wie ich auf diese Zahl kam damals.
--
Gruß
Matthias
|
|
|
| |
|
hmm!
also ich versuche das mal zu erläutern und zu verstehen
meine liste ist folgendermaßen:
8 4 5 1 2 7 3 6
4 8
5 1
1 4 5 8
2 7
3 6
2 3 6 7
1 2 3 4 5 6 7
So sollte doch bei Mergesort sortiert werden. Richtig?
Wenn ich nun 4 und 8 vergleiche entspricht doch das einer Vergleichoperation!
Bei 6 und 1 das gleiche. wenn ich nun die beiden Teilfolgende verglichen habe vermische ich sie. a und nun muß doch jede Zahl mit jeder Verglichenwerden, damit sie korrekt stehen. Oder ist das gerade mein Holzweg. Das währe ja dann wie bubblesort.
Also wie arbeited dann mergersort, wenn die beiden Teilfolgen 4 8 und 5 1 vermischt und sortiert werden?
Gruß Georg
|
|
|
| |
|
Hallo Georg!
Und so etwas macht man erst im Hauptstudium?  Also ich habe das gestern an der Tafel mit meinen Info IV Studenten durchgerechnet.
Ich glaube, ein Teil deines Ansatzes ist schon richtig, aber ich versuch's trotzdem mal ganz von vorne:
Du hast die Liste 8 4 5 1 2 7 3 6.
Im ersten Schritt wird sie in zwei vierelementige Listen geteilt:
8 4 5 1 und 2 7 3 6
Im zweiten Schritt wird jede dieser vierelementigen Listen in zwei zweielementige Listen geteilt:
aus 8 4 5 1 werden 8 4 und 5 1
aus 2 7 3 6 werden 2 7 und 3 6
Im dritten Schritt wird jede dieser zweielemtigen Listen in zwei einelementige Listen geteilt, du hast also 8 einelementige Listen:
8 4 5 1 2 7 3 6
Nun wird "gemergt":
Die einelementige Liste 8 wird mit der einelementigen Liste 4 zusammengefügt. Dafür werden 8 und 4 Verglichen [mm] \to [/mm] 1 Vergleich. Die Ergebnisliste ist:
4 8.
Im gleichen Merge-Schritt wird die Liste 5 mit der Liste 1 zusammengemischt. Dafür wird die 5 mit der 1 verglichen [mm] \to [/mm] wieder 1 Vergleich. Die Ergebnisliste ist 1 5.
Im selben Schritt wird das gleiche mit den Listen 2 und 7 und den Listen 3 und 6 gemacht - dafür brauchst du jeweils einen Vergleich, du hast also im ersten Schritt insgesamt 4 Vergleiche. Dann hast du dort vier zweielementige Listen stehen:
4 8 1 5 2 7 3 6
Nun werden die Listen 4 8 und 1 5 zusammengefügt. Der erste Vergleich ist: 4 und 1. 1 ist kleiner, also kommt sie nach links. Dann werden verglichen: 4 und 5. 4 ist kleiner, also kommt sie neben die 1. Dann werden 5 und 8 verglichen, 5 ist kleiner, also kommt sie daneben, und dann bleibt nur noch die 8 übrig. Du siehst, dass nicht jedes Element mit jedem verglichen wird. Das kommt daher, dass die zweielementigen Listen ja schon sortiert waren. Wenn also die 4 schon kleiner als die 8 ist, und du im ersten Vergleich erhältst, dass die 4 größer als die 1 ist, dann muss natürlich auch die 8 größer als die 1 sein, du brauchst also 8 und 1 gar nicht mehr vergleichen.
So, in diesem Schritt haben wir bisher 3 Vergleiche gebraucht.
Nun werden noch die Listen 2 7 und 3 6 zusammengefügt. Das geht ganz genauso und wir haben nochmal 3 Vergleiche, das ergibt dann für den zweiten Schritt insgesamt 6 Vergleiche.
Nun haben wir nur noch zwei Listen, die wir zusammenfügen müssen:
1 4 5 8 und 2 3 6 7
1. Vergleich: 1 und 2
$1<2 [mm] \to [/mm] 1$ nach links, nächster Vergleich: 2 und 4
$2<4 [mm] \to [/mm] 2$ neben die 1, nächster Vergleich: 4 und 3
$3<4 [mm] \to [/mm] 3$ neben die 2, nächster Vergleich: 4 und 6
$4<6 [mm] \to [/mm] 4$ neben die 3, nächster Vergleich: 6 und 5
$5<6 [mm] \to [/mm] 5$ neben die 4, nächster Vergleich: 6 und 8
$6<8 [mm] \to [/mm] 6$ neben die 5, nächster Vergleich: 8 und 7
$7<8 [mm] \to [/mm] 7$ neben die 6, kein Vergleich mehr nötig, da nur noch die 8 übrig ist
[mm] $\to [/mm] 8$ neben die 7 und die sortierte Folge ist - oh Wunder:
1 2 3 4 5 6 7 8
Im diesem letzten Schritt haben wir also insgesamt 7 Vergleiche gebraucht. Das macht dann zusammen: 4+6+7=17 Vergleiche. (Ich weiß nicht, wie Matthias auf 12 kommt... ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]") )
Nun klar, wie das Ganze funktioniert? ![[]](/images/popup.gif) Hier gibt es auch noch "unser" aktuelles Skript - ich fand es ziemlich gut, da sind auch allgemein viele lustige Bildchen drin.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
