Mergesort - Aufteilen bei ungerader Länge

[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

[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

[AnnaW]

Danke für die Antwort

[Malte]

Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante und .

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 of the length of s'. Consequently, the lengths of s1' and s2' are at least 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?

[jw.]

Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante und .

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

[Malte]

Okay, dann lag da mein Fehler, hab es mir wohl falsch rum gemerkt
Danke vielmals, dann habe ich nichts gesagt