Kurs Diskussion:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort

Parameterreihenfolge

Für die Prozedur "MergeSortRek" wird in Zeile 5 definiert:

 5.     PROCEDURE MergeSortRek ( VAR a, b : ARRAY OF LONGINT ; von, bis : LONGINT );

Nach meinem Verständnis also zuerst das Array "a", danach das Array "b", dann die Longint-Werte "von" und "bis". In Zeile 19 steht:

19.                 MergeSortRek(b,a,von,m); MergeSortRek(b,a,m+1,bis);

Also ein Aufruf, wo zuerst das Array "b" und erst danach das Array "a" übergeben wird. Analog in Zeile 39:

39.         MergeSortRek(b^,a,0,n-1);

Auch hier wird zuerst "b" und danach "a" übergeben. Ist das korrekt so oder sind die Variablenbezeichnungen hier vertauscht? --Exxu 16:58, 7. Nov. 2006 (CET)

Hi Exxu! Das ist nicht nur korrekt sondern sogar Absicht :) Das Problem bei Mergesort -- wenn man nicht mit Pointers herumhantieren will -- ist dass die Daten immer vom Array a nach dem Array b geschoben werden. Sortiert man aber die Teilarrays, wollen wir, dass das Resultat in a bleibt. Vor dem Aufruf der Rekursion kopiere ich a in b damit es nicht darauf ankommt, woher man die Daten liest, sie werden aber so immer von einem Array ins andere kopiert und landen am Schluss so in a. Ich musste an einem Talk und konnte deswegen die Erklaerung dazu noch nicht schreiben, man vermeidet aber so, dass man am Ende von MergeSortRek die Daten von b nach a wieder zurueckkopieren muss! Cheers und Danke fuers aufmerksame -- und prompte! -- lesen :) --Pedro.Gonnet 17:07, 7. Nov. 2006 (CET)

Danke für die Erläuterung. Ich bin darauf aufmerksam geworden, weil ich gerade darüber sitze, diesen Algortihmus mal in Java zu schreiben. Gruß --Exxu 17:15, 7. Nov. 2006 (CET)

MergeSort in Java

Hallo Exxu! Deine Java-Implementation entspricht nicht gerade dem Standard-Mergesort... Die kann bei der Berechnung des asymptotischen Verhaltens eine grosse Rolle spielen. Kannst Du noch dein altes MergeSort wieder hochschalten und die verbesserte Version als Alternative markieren? Es geht mehr darum, Standardverfahren zu zeigen und weniger darum, dass diese zu optimieren (sonst haetten wir den lieben BubbleSort auch nicht drin) ;) Cheers, Pedro.Gonnet 11:40, 9. Nov. 2006 (CET)

Kommentare farbig?

Hallo, zum Lesen von Sourcecode wäre es hilfreich, wenn Kommentare andere Stile (Farbe und/oder Schrift,...) haben. Kann man sich da im Kolloquium evtl. auf was einigen? --Erkan Yilmaz 05:40, 10. Nov. 2006 (CET)

Wie ich sehe hat Exxu wieder mal Vorarbeit geleistet :-) siehe hier. --Erkan Yilmaz 10:35, 12. Nov. 2006 (CET)

andere Sprachen

Hier mal Beispiele auch mit anderen Sprachen in der Wikipedia: [1]. Zumindest die Pascal-Variante könnte auch aufgelistet werden?

Im Wikibooks zu C wurde das mal angedacht. Kann man ja in Zukunft entweder von hier oder von dort dann übertragen. --Erkan Yilmaz 06:19, 10. Nov. 2006 (CET)

Habe mal die anderen Sprachen auch eingefügt und mit "(Wikipedia)" markiert. An Kursleiter: bitte entsprechend anpassen. INteressant wäre es jetzt auch mal, die beiden Java-Versionen zu vergleichen :-) --Erkan Yilmaz 10:32, 12. Nov. 2006 (CET)

unvollständige Induktion

Der angeführte Beweis ist nicht vollständig. Denn zur "vollständigen Induktion" muss Deine kühne Behauptung auch für den Anfangswert gelten. Wenn Du aber als Anfangswert K(1) = 1, also K(2^0) = 1, betrachtest, dann ist in diesem Falle i=0. Für i=0 stimmt aber die allgemeine Formel nicht, denn K(2^0) = 1 ungleich 0*2^0 = 0*1 = 0.

Anders ausgedrückt, die allgemeine Formel stimmt erst für natürliche Werte i >= 1 bzw. K(2^i) mit i>=1. Was uns natürlich ausreicht. (Aber Mathematiker nehmens nun mal pingelig ;-)) --Exxu 18:03, 13. Nov. 2006 (CET)

Hast Recht -- hab eine Grippe und hab wahrscheinlich zuviele Medis geschluckt ;) Cheers und danke! --Pedro.Gonnet 19:04, 13. Nov. 2006 (CET)

Na denn - Gute Besserung! :) --Exxu 20:17, 13. Nov. 2006 (CET)