Seite 1 von 1

Mergesort - Aufteilen bei ungerader Länge

Verfasst: 20. Mai 2013 19:43
von AnnaW
Hallo,

ich habe kurz ein Frage zur Aufteilung der Sequenz. Wenn ich jetzt, wie in der Übung, eine Sequenz mit 9 Elementen habe, hält dann S1 4 oder 5 Elemente? Wie wird da geteilt? Auch im nächsten Schritt, wenn der Teil mit 5 Elementen geteilt wird, hab ich dann 2 - 3 oder 3 - 2 Elemente? Ich kann dazu leider nichts finden.

Viele Grüße

Anna

Re: Mergesort - Aufteilen bei ungerader Länge

Verfasst: 20. Mai 2013 20:06
von JannikV
Hey, du kannst dir aussuchen ob du immer die linke oder immer die rechte Seite größer sein lassen willst.
Im Wiki steht ja nur: The sequence is divided into two subsequences of approximately half size, it does not matter at all in which way this is done.

VG

Re: Mergesort - Aufteilen bei ungerader Länge

Verfasst: 20. Mai 2013 20:58
von AnnaW
Danke für die Antwort :-)

Re: Mergesort - Aufteilen bei ungerader Länge

Verfasst: 20. Mai 2013 22:18
von Malte
Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante Bild und Bild.

Ist das richtig, dass beide Terme in Gaußen Abrundungsklammern stehen? Wenn beide Teile einer ungeraden Sequenz halbiert und abgerundet werden, dürfte dabei doch ein Element verloren gehen.


Im Beweis steht dann das hier:
"So, the lengths of s1' and s2' are at most Bild of the length of s'. Consequently, the lengths of s1' and s2' are at least Bild of the length of s'"

heißt s1' und s2' haben höchstens die abgerundete halbierte, aber gleichzeitig mindestens die aufgerundete halbierte Länge von s'? Also im Beispiel von s' mit Länge 9 hätten s1' und s2' höchstens Länge 4 und mindestens Länge 5?

Re: Mergesort - Aufteilen bei ungerader Länge

Verfasst: 20. Mai 2013 23:21
von jw.
Malte hat geschrieben:Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante Bild und Bild.

Ist das richtig, dass beide Terme in Gaußen Abrundungsklammern stehen? Wenn beide Teile einer ungeraden Sequenz halbiert und abgerundet werden, dürfte dabei doch ein Element verloren gehen.
Du verwechselst Auf- und Abrundungsfunktion, siehe Wikipedia:
http://de.wikipedia.org/wiki/Abrundungs ... gsfunktion

Re: Mergesort - Aufteilen bei ungerader Länge

Verfasst: 21. Mai 2013 08:16
von Malte
Okay, dann lag da mein Fehler, hab es mir wohl falsch rum gemerkt :-)
Danke vielmals, dann habe ich nichts gesagt ;-)