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
Mergesort - Aufteilen bei ungerader Länge
Re: Mergesort - Aufteilen bei ungerader Länge
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
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
Danke für die Antwort 

Re: Mergesort - Aufteilen bei ungerader Länge
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?
Im Wiki steht unter Abstract view in der Variante
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
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
Du verwechselst Auf- und Abrundungsfunktion, siehe Wikipedia:Malte hat geschrieben:Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Varianteund
.
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.
http://de.wikipedia.org/wiki/Abrundungs ... gsfunktion
Re: Mergesort - Aufteilen bei ungerader Länge
Okay, dann lag da mein Fehler, hab es mir wohl falsch rum gemerkt 
Danke vielmals, dann habe ich nichts gesagt

Danke vielmals, dann habe ich nichts gesagt
