Einfache Mergesort Implementierung

[Thunderbolt]

Ich soll für die Schule nen kleinen Vortrag vorbereiten, in dem ich den anderen Erklär wie Mergesort funktioniert. Das Prinzip ist ja relativ simpel - man "spaltet" die Daten aus nem Array (in unserem Beispiel kanns ein vorbelegtes Array mit irgendwelchen Zahlen sein) bis man diese in vielen eine-zahl-arrays hat und diese werden dann wie beim externen sortieren mit Bandmaschinen "verschmolzen" bis man wieder ein Array hat, nur diesmal sortiert.
Hört sich in der Theorie alles ganz einfach an, aber wie implementiert ich so was? Muss ich jetzt irgendwie rekursiv in der Laufzeit neue Arrays anlegen oder ist das überhaupt nicht nötig? :wall:
Könnte mir jemand mit ner einfachen Konsolenanwendung auf die Sprünge helfen?

[toms]

Hallo

Stichwort: Google

[Thunderbolt]

Danke. Sehr hilfreiche Antwort...

Ich hab da nen kleinen Text auf die Reihe bekommen, nur schein ich da noch irgendwas nicht richtig gemacht zu haben. Könnte mir jemand das offensichtliche vor die Augen führen? :gruebel:

Delphi-Quellcode:

program Mergesortierdemoprogramm;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const n=30;

var
zufall :array [1..n] of integer;
i :integer;


procedure mergen(Links, MitteLinks, MitteRechts, Rechts :integer; var beispielarray: array of integer);
var
  hilf :array of integer; // Zum mergen der Arrays = Ergebnis
  index_hilf, index_links, index_rechts :integer;
  // Hilfsindex, Laufindezes für die Arrays
begin
  setlength(hilf,(mittelinks-links+1)+(rechts-mitterechts+1));
  //Länge des Arrays berechnen
  index_links:=links;     //Startwerte der Laufindezes setzen
  index_rechts:=rechts;   //Jeweils auf dem Linken Teil

  //Verschmelz-Vorgang
  for index_hilf:=low(hilf) to high(hilf) do //Durchlaufen des Hilfsarrays
  begin
    //Überprüfung, ob beide "Bereiche" noch Elemente haben
    if ((index_links<=MitteLinks) and (index_rechts<=rechts)) then
      begin
        if (beispielarray[index_links]< beispielarray[index_rechts]) then
          begin
            hilf[index_hilf]:=beispielarray[index_links];
            inc(index_links);
          end
        else
          begin
            hilf[index_hilf]:=beispielarray[index_rechts];
            inc(index_rechts);
          end;
      end
    //Fall "beide haben Elemente" abgearbeitet!
    //nächster Fall: hat der linke noch Elemente?
    else if (index_links <=mittelinks) then
      begin
        hilf[index_hilf]:=beispielarray[index_links];
        inc(index_links);
      end
    //Fall "NUR links hat Elemente abgearbeitet!
    //nächster Fall: hat der rechte evtl. Elemente?
    else if (index_rechts<=rechts) then
      begin
        hilf[index_hilf]:=beispielarray[index_rechts];
        inc(index_rechts);
      end;
    //Der einzige überig bleibende Fall ist, dass beide schon
    //abgearbeitet sind. Kommt nicht in der Schleife zustande!
  end;

    //Letzter Schritt: in die zwei Bereiche zurückkopieren!!!

  index_hilf:=low(hilf);
  for index_links:=links to mittelinks do
  begin
    beispielarray[index_links]:=hilf[index_hilf];
    inc(index_hilf);
  end;
  for index_rechts:=mitterechts to rechts do
  begin
    beispielarray[index_rechts]:=hilf[index_hilf];
    inc(index_hilf);
  end;

end;

procedure sortiere(anfang, ende :integer; var beispielarray: array of integer);
// Übergabe der "Schranken"
var mitte :integer; // Variable zur bestimmung der Arraymitte
begin
  if anfang<ende then //Abbruchbedingung: array mehr als 1 Element
  begin
    mitte:= (anfang+ende) div 2; // Bestimmung der Mitte des Arrays

    sortiere(anfang,mitte,beispielarray); //"Linker" Teil wird sortiert
    sortiere(mitte+1,ende,beispielarray); //"Rechter" Teil wird sortiert
    // Verschmelzen der zwei sortierten Bereiche!
    mergen(Anfang,Mitte,Mitte+1,Ende,beispielarray);
  end;
end;

procedure mergesort(var beispielarray: array of integer);
begin                        // Aufruf mit Übergabe des
  sortiere(low(beispielarray),high(beispielarray),beispielarray);   // zu bearbeitenden Arrays
end;                         // Aufruf der Unterprozedur
                             // mit Übergabe der "Schranken"
begin
  randomize;
  for i:=1 to n do zufall[i]:=random(n);
  writeln('Ausgangsfeld:');
  for i:=1 to n do write(zufall[i],',');
  writeln; writeln;
  mergesort(zufall);
  writeln('Sortiertes Feld:');
  for i:=1 to n do write(zufall[i],',');
  readln;
end.

[Elvis]

Hi, schaue mal hier vorbei.
Der Source code ist zwar Java, aber sehr einfach gehalten. Dafür sind die Erklärungen super und es ist sogar ein kleines Java Applet dabei, das das Prinzip erklärt. :)

[Thunderbolt]

gnarf. danke, die erklärungen auf der seite kann ich verwerten, aber den quelltext suchen se nicht nach fehlern ab. find meinen fehler immer noch nicht :(

[Thunderbolt]

*push* hat niemand ne Idee?

[Klaus01]

na, vielleicht schreibsr Du mal was für ein Fehler Dein Programm hat.
Dann findet der ein oder andere besser einen Ansatz Dir zu helfen.

Hier ist ein MergeSort das Deinem recht ähnlich sieht:
Die Bezeichnungen sind anders - aber sonst ist recht gleich.

Delphi-Quellcode:

program MergeSort;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const n=30;

var
zufall :array [0..n-1] of integer;
i :integer;


procedure MergeSort(var A: array of Integer);

  (* Es werden zwei sortierten Bereiche des Arrays ineinander gemergt. *)

  procedure Merge(LoL, HiL, LoR, HiR: Integer);
  var
    SA: array of Integer; // Hilfsarray: die 2 Bereiche werden hier reingemergt!
    SI: Integer;          // Index für das Hilfsarray
    IL, IR: Integer;      // Lauf-Indezes der beiden Teilbereiche
  begin
    // Initialisierung
    // Das Hilfsarray SA mit der Länge beider Bereiche
    SetLength(SA, (HiL - LoL + 1) + (HiR - LoR + 1));
    // Die Laufvariablen beginnen jeweils mit dem niederwertigen Bereichsindex.
    IL := LoL;
    IR := LoR;

    // Der eigentliche Merge-Vorgang!
    for SI := Low(SA) to High(SA) do
    begin
      // Haben beide Bereiche noch Elemente?
      if ((IL <= HiL) and (IR <= HiR)) then
      begin
        if (A[IL] < A[IR]) then
        begin
          SA[SI] := A[IL];
          Inc(IL);
        end
        else
        begin
          SA[SI] := A[IR];
          Inc(IR);
        end;
      end
      // Andernfalls: Hat der linke Bereich noch Elemente?
      else if (IL <= HiL) then
      begin
        SA[SI] := A[IL];
        Inc(IL);
      end
      // Andernfalls: Hat der rechte Bereich noch Elemente?
      else if (IR <= HiR) then
      begin
        SA[SI] := A[IR];
        Inc(IR);
      end;
      // Andernfalls: Beide Breiche sind schon abgearbeitet!
      // Dieser Fall kommt aber nicht innerhalb dieser Schleife nicht zustande!
    end;

    // Finalisierung: SA wird wieder in die zwei Bereiche zurückkopiert!
    SI := Low(SA);
    for IL := LoL to HiL do
    begin
      A[IL] := SA[SI];
      Inc(SI);
    end;
    for IR := LoR to HiR do
    begin
      A[IR] := SA[SI];
      Inc(SI);
    end;
  end;

  (* Der MergeSort mit den Bereichsgrenzen *)

  procedure MSort(Lo, Hi: Integer);
  var
    Middle: Integer;
  begin
    if (Lo < Hi) then
    begin
      Middle := (Lo + Hi) div 2;

      MSort(Lo, Middle);     // Linker Bereich wird sortiert
      MSort(Middle + 1, Hi); // Rechter Bereich wird sortiert

      // Die zwei sortierten Bereiche werden ineinander gemergt!
      Merge(Lo, Middle, Middle + 1, Hi);
    end;
  end;

begin
  MSort(Low(A), High(A));
end;

begin
  randomize;
  for i:=0 to n-1 do zufall[i]:=random(n);
  writeln('Ausgangsfeld:');
  for i:=0 to n-1 do write(zufall[i],',');
  writeln; writeln;
  mergesort(zufall);
  writeln('Sortiertes Feld:');
  for i:=0 to n-1 do write(zufall[i],',');
  readln; 
end.

Grüße
Klaus

[Thunderbolt]

grml. hab den fehler gefunden.

Delphi-Quellcode:

index_links:=links;     //Startwerte der Laufindezes setzen
  index_rechts:=rechts;   //Jeweils auf dem Linken Teil

sonst gings mir gut...
schreib mir noch extre hin auf dem linken teil und setz index_rechts auf den letzten wert des arrays :wall:

wenn ich demnächst son programm schreiben muss klau ich mir was ausm internet und lass über die suchfunktion alle variablen umbenennen ist sicherer :D