Mergesort quellcode

[Koby]

Hallo Leute ,
ich wollte euch mal was fragen! Ich habe einen Code gefunden möchte ihn aber verstehen!
Könnte mir mal jemand den code Kommentieren, damit ich den code verstehe, da ich ihn verstehen
möchte! (den Code füge ich hinzu als datei)


Also würde mich freuen über jegliche Erklärungen!!!


P.S. Bin neu hier, hoffe aber was ich schon gesehen habe is das hier ne geile community

[Bernhard Geyer]

Mergesort bei Wikipedia

[hanselmansel]

Um dir etwas wärmstens ans Herz zu legen: Vergiss den geposteten Code. Der mag besser aussehen, weil er so schön lang ist, aber daniels Code ist nicht nur richtiger, sondern bietet auch mehr Möglichkeit zu lernen. Und noch ein Tipp: Nimm dir irgendeinen Code vor, dazu ein Blatt Papier, und spiel ihn einfach mal durch. Daran sieht man am besten, wie er funktioniert.

[Koby]

genauer gesagt das ist mein code von meinem programm was könnte ich verbessern

[Der_Unwissende]

Zitat von hanselmansel:

Um dir etwas wärmstens ans Herz zu legen: Vergiss den geposteten Code. Der mag besser aussehen, weil er so schön lang ist, aber daniels Code ist nicht nur richtiger, sondern bietet auch mehr Möglichkeit zu lernen. Und noch ein Tipp: Nimm dir irgendeinen Code vor, dazu ein Blatt Papier, und spiel ihn einfach mal durch. Daran sieht man am besten, wie er funktioniert.

Wurde Koby glaube ich schonmal empfohlen. Gibt noch einen zweiten Thread in dem er nach Code für den Mergesort gesucht hat. Da die DP-Regeln aber das lösen von Hausaufgaben (im anderen Thread wurde davon ausgegangen, dass es sich um welche handelt) ablehnt, ist es wohl nicht Daniels Code gewurden.
Möchte hier auch nur noch mal darauf hinweisen, bevor jmd. Code postet.

@Koby, wie du siehst kommt auch hier der Tipp es einfach mal auf Papier durch zu spielen, dann verstehst du einfach schon ganz gut, wie Mergesort funktioniert. Wenn du dann dazu konkrete Fragen hast, stell sie.

Gruß Der Unwissende

[hanselmansel]

@ Der_Unwissende: Habe den Post falsch verstanden. Dachte, der Code wäre aus einer anderen Internet-Quelle. In diesem Fall gucken wir uns den Code doch mal genauer an.

Delphi-Quellcode:

procedure TSortierverfahren.Mergesort(var List:array of integer);
var
  laenge,x,y,z        :integer;
  h_array1, h_array2  :array of integer;

begin
//Anzahl der zu sortierenden Elemente bestimmen
laenge:= length(List);
//Die Hilfsfelder auf halbe Länge dimensionieren
Setlength (h_array1, laenge div 2);
Setlength (h_array2,(laenge + 1) div 2);

//Zahlen aus der 1. Hälfte des Quellarray ins 1. Hilfsarray kopieren
for x:=0 to laenge div 2 - 1 do
  h_array1[x]:=List[x];

//Das gleiche für's 2. Hilfsarray...
for y:=0 to (laenge + 1) div 2 - 1 do
  h_array2[y]:=List[y+((laenge) div 2)];

//Wenn die Feldlänge > 2, dann rufe die Prozedur rekursiv auf.
if laenge > 2 then
  begin
  mergesort(h_array1);
  mergesort(h_array2);
  end;
z:=0;

//in die Abfrage muss ein OR...
while (length(h_array1) <> 0) and (length(h_array2) <>0) do
  begin
  //Das oberste Element vom kleineren Stapel auswählen...
  If h_array1[0] < h_array2[0] then
    Begin
    //...und ins Quellarray zurückschreiben
    List[z] := h_array1[0];

    //alle Array-Elemente um 1 nach vorne schieben
    for x:=0 to length(h_array1)-2 do
      h_array1[x]:=h_array1[x+1];

    //Array verkleinern *kreisch*
    Setlength (h_array1,length(h_array1)-1);
    end
  Else
    //the same in green...
    begin
    List[z]:=h_array2[0];

    for y:=0 to length(h_array2)-2 do
      h_array2[y]:=h_array2[y+1];

    setlength(h_array2,length(h_array2)-1);
    end;
  z:=z+1;
  end;

{Nach dem Durchlauf der Schleife ist eins der Hilfsfelder auf jeden Fall leer.
Wenn das andere noch Elemente enthält, dann wird es komplett ins Quell-Array
geschrieben.}

if length(h_array1)<>0 then
  for x:=0 to length(h_array1)-1 do
    begin
    List[z]:=h_array1[x];
    z:=z+1;
    end;

if length(h_array2)<>0 then
  for y:=0 to length(h_array2)-1 do
    begin
    List[z]:=h_array2[y];
    z:=z+1;
    end;

end;

Ich habe im Code mal kommentiert, was er überhaupt im Großen macht, damit du verstehst, was du gecodet hast. Hierbei habe ich (abgesehen von der While-Schleife) kein Augenmerk auf die Richtigkeit des Codes gelegt, und noch nicht mal geprüft, was davon funktioniert. (Denn funktionieren kann er praktisch noch nicht ) Wenn du den kommentierten Code gelesen hast, kannst du dich ja noch mal melden. Dann gehen wir die inhaltlichen "Ungereimtheiten" des Codes an...

MfG,

hanselmansel

[Koby]

ersteinmal voll korekt von dir hanselmann das du auf mein problem eingegangen bist!!!!

Und dann wollt ich mal sagen das das programm funktioniert so wie es da steht!



//in die Abfrage muss ein OR...
while (length(h_array1) <> 0) and (length(h_array2) <>0) do

wieso muss da ein or hin, es funktioniert auch ohne???!

[hanselmansel]

Vergiss die Sache mit dem OR... hab mich im Code verlesen.

[Koby]

und waas bewirkt das kommentiert grob


procedure TSortierverfahren.Enter_bClick(Sender: TObject);
begin
Sortierverfahren.nsortiert_lb.items.add(eingabefel d_e.text);
Setlength (nsortiert,Elemente+1);
nsortiert[Elemente] := (StrToInt(eingabefeld_e.text));
Elemente:=Elemente+1;
Sortierverfahren.eingabefeld_e.text :='';
end;

procedure TSortierverfahren.Sort_bClick(Sender: TObject);
var
i:integer;
begin
Sortierverfahren.Mergesort(nsortiert);
for i:= 0 to Elemente-1 do
begin
Sortierverfahren.sortiert_lb.items.add(IntToStr(ns ortiert[i]));
end;
end;



und beim merge sort diese stelle noch die ich nicht ganz ralle unterre teil


if length(h_array1)<>0 then
for x:=0 to length(h_array1)-1 do
begin
List[z]:=h_array1[x];
z:=z+1;
end;

if length(h_array2)<>0 then
for y:=0 to length(h_array2)-1 do
begin
List[z]:=h_array2[y];
z:=z+1;
end;

[hanselmansel]

Bitte setzte um deinen Code Delphi-Tags. Dann wird er schön vom Forum formatiert und man kann ihn auch lesen, wenn man nicht a priori wusste, was drin steht.
Die oben angesprochene Schleife bricht ab, sobald eine der Listen leer ist. Das heißt aber auch, dass in der anderen Liste noch etwas drin stehen kann. Darauf wird in diesem Teil des Codes geprüft, um anschließend die Elemente zu kopieren.

MfG,

hanselmansel