Mergesort vs. bubblesort Demo (Prob. m. Mergesort)

[Coder]

Ich habe nun ein Programm geschrieben, was mir BubbleSort und Mergesort vergleicht.

Zudem verschiebe ich nicht die Arrays in Records, sondern sortiere nur die Indizes.
Allerdings habe ich mich dort wohl etwas verheddert.
Ich hoffe, daß jemand von Euch den Fehler findet.
Irgendwie Sortiert er mir, wenn ich meine nach Name zu sortieren, nach Size ... und das dürfte ja nicht sein.

Ich habe, um das Programm schneller zu machen das Stringgrid aus dem Code (auf der Wikipediahomepage) entfernt und durch meinen Record ersetzt.

Damit Ihr Euch ein Bild von dem Programm machen könnt habe ich

Die Funktion
http://membres.lycos.fr/real746/delp.../mergesort.htm
sowie das ganze Projekt (Source) als .zip Datei raufgeladen
http://membres.lycos.fr/real746/delphi/mergesort/ << Hauptseite

INFO: Das Programm wird wie folgt verwendet: 1) Button Record füllen drücken, dann 2) den Button für den Algorithmus wählen

http://de.wikipedia.org/wiki/Mergesort#Pascal
( Wikipedia-Seite, die beschreibt, wie der
MergeSort-Algorithmus arbeitet und implementiert wird , u.a. in Pascal)

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, inifiles, Menus;


type
  MyRecord = record
    Name: string;
    Datum: string;
    Size: Integer;
    std: Byte;
  end;

  TForm1 = class(TForm)
    Bubble_Sort: TButton;
    EXIT_Btn: TButton;
    Fill_list_btn: TButton;
    Memo1: TMemo;
    Merge_Sort_Btn: TButton;
    Label1: TLabel;
    MainMenu1: TMainMenu;
    about: TMenuItem;
    procedure Bubble_SortClick(Sender: TObject);
    procedure Zeigmir(const Was: Integer);
    procedure EXIT_BtnClick(Sender: TObject);
    procedure Fill_list_btnClick(Sender: TObject);
    procedure FormKeyDown(Sender: TObject; var Key: Word;
      Shift: TShiftState);
    procedure Merge_Sort_BtnClick(Sender: TObject);
    procedure AboutClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    Records: array[0..1000] of MyRecord;
      Index: array[0..1000] of Integer;
    RecordCount: Integer;
    hilf: array[0..300] of Integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Zeigmir(const Was: Integer);
var
  i: Integer;
begin
  i := Index[Was]; // umschlüsseln
  With form1.Memo1 do begin
       Lines.Add(' Index: ' + IntToStr(Was) + ' Index[Stelle]: '   + IntToStr(i) );
       Lines.Add( form1.Records[i].Name);
       Lines.Add( 'Datum: ' + (form1.Records[i].Datum)+ 'Size: ');
       Lines.Add( 'Size: ' + IntToStr(form1.Records[i].Size) );
  end;
end;

procedure MergeSort_String(links, rechts: integer);
var i, x, y, z, mid: integer;
  hilfs: array[0..1000] of string;
//    hilf: array of integer;
begin
  if (rechts - links > 0) then //Abbruchbedingung
  begin
    mid := (rechts + links) div 2; //Mitte bestimmen

    MergeSort_String(links, mid);
    MergeSort_String(mid + 1, rechts);

    for x := mid downto links do                       //Werte in das
      hilfs[x] := form1.Records[form1.Index[x]].Name;  //dynamische Array
    for y := mid + 1 to rechts do                      //schreiben
      hilfs[rechts + mid + 1 - y] := form1.Records[form1.Index[y]].Name;

    x := links;
    y := rechts;

    for z := links to rechts do
    begin
      if hilfs[x] < hilfs[y] then                                        //Datensätze
      begin //sortieren
        form1.Records[form1.Index[y]].Name := (hilfs[x]);
        inc(x);
      end // then
      else //geteilte Datensätze
      begin //wieder verschmelzen ("mischen")
        form1.Records[form1.Index[y]].Name := (hilfs[y]);
        dec(y);
      end; // else
    end; // for
  end // then
end;

procedure TForm1.Bubble_SortClick(Sender: TObject);
var
  Max, i, j: Integer;

  procedure SwapIndex(const Position: Integer);
  var
    temp: Integer;
  begin
    temp := Index[Position];
    Index[Position] := Index[Position + 1];
    Index[Position + 1] := temp;
  end;

begin
  Max := 10;
  form1.Memo1.Lines.Clear;
  for i := 0 to Max - 1 do
    Index[i] := i;
  // Ausgabe
//  ShowMessage('unsortiert');
  for i := 0 to MAX - 1 do
    Zeigmir(i);
  Memo1.Text := Memo1.Text + #13#10 + '--- Name ----' + #13#10;
  // Index nach Namen sortieren (BubbleSort)
  for j := MAX - 1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Name > Records[Index[i + 1]].Name) then
        SwapIndex(i);
  for i := 0 to MAX - 1 do
    Zeigmir(i); // Ausgabe  //  ShowMessage('Nach Namen');
  // Index nach Size sortieren (BubbleSort)
  for j := MAX - 1 downto 0 do
    for i := 0 to j do
      if StrtoDatetime((Records[Index[i]].Datum)) > StrtoDatetime(Records[Index[i + 1]].Datum) then
        SwapIndex(i);
  // Ausgabe //  ShowMessage('Nach Size');
  Memo1.Text := Memo1.Text + #13#10 + #13#10 + '--- Datum ----' + #13#10;
  for i := 0 to MAX - 1 do
    Zeigmir(i);
  // Ausgabe
  for j := MAX - 1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Size > Records[Index[i + 1]].Size) then
        SwapIndex(i);
  // Ausgabe  //  ShowMessage('Nach Size');
  Memo1.Text := Memo1.Text + #13#10 + #13#10 + '--- size ----' + #13#10;
  for i := 0 to MAX - 1 do
    Zeigmir(i);

end;

procedure TForm1.EXIT_BtnClick(Sender: TObject);
begin
  Close;
end;

procedure TForm1.Fill_list_btnClick(Sender: TObject);
var
  y, x, i: integer;
  a: string;                        // Hier werden eigentlich nur Zufallswerte
  inidat: TIniFile;                 // in die Records[] geschrieben
begin
  // Werte vorbelegen
  Randomize;
  for i := 0 to 1000 do begin // Namen füllen
    a := '';
    x := 0;
    repeat
      inc(x);
      y := random(1);
      case y of
        0: a := a + chr(Random(26) + 97);
        1: a := a + chr(Random(26) + 65);
      end;
      a := a + chr(Random(26) + 65);
    until x > 10;
    Records[i].Name := a;
  end;
///////////////////////////////////////////////////////////
  for i := 0 to 1000 do begin // Datum füllen
    a := '';
    a := a + IntToStr(Random(10) + 10) + '.' + IntToStr(Random(12) + 1) + '.' + IntToStr(Random(30) + 1970)
      + ' ' + IntToStr(Random(14) + 10) + ':' + IntToStr(Random(49) + 10) + ':' + IntToStr(Random(49) + 10);
    Records[i].Datum := a;
  end;
//   Records[0].Datum := '01.05.2003 16:04:28';
///////////////////////////////////////////////////////////
  for i := 0 to 1000 do // Size füllen
     begin
       y := Random(2600) + 1;
       Records[i].Size := y;
     end;
end;


procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word;
  Shift: TShiftState);
begin
  if key = Vk_F4 then
end;

procedure ZeigmirMerge(const Was: Integer);
var
  i: Integer;
begin
  i := form1.Index[Was]; // umschlüsseln
  With form1.Memo1 do begin
  Lines.Add(' Index: ' + IntToStr(Was) + ' Index[Stelle]: '   + IntToStr(i) );
  Lines.Add( form1.Records[i].Name);
  Lines.Add( 'Datum: ' + form1.Records[i].Datum);
  Lines.Add( 'Size: ' + IntToStr(form1.Records[i].Size) );
  end;
end;

procedure TForm1.Merge_Sort_BtnClick(Sender: TObject);
var x, i, links, mid, rechts: integer;
begin
  links := 0;
  rechts := 10;
  mid := (rechts + links) div 2; //Mitte bestimmen
  MergeSort_String(links, rechts);
      form1.Memo1.Lines.Clear;
  for i := 0 to 10 do
    ZeigmirMerge(i);

end;

end.

[Der_Unwissende]

Hi,
also ehrlich gesagt ist dass eine doch eher ungewöhnliche Implementierung des Mergesort. Ich weiß ja nicht was du genau vergleichen möchtest, aber wenn es um die Asympotischen Laufzeiten geht (die bei Mergesort theoretisch besser ist), dann solltest du nicht mit gerade einmal 1000 Datensätzen arbeiten. In dieser Laufzeit sind verschiedene Konstanten versteckt und die deutlichen Unterschiede kommen erst in Großendatenbereichen (bin mir nicht sicher ob 1000 Datensätze da schon reichen).

Zudem wirkt auf den ersten Blick deine Mergesortimplentierung ein wenig in-place, dass wäre zwar schön, nur ist der Mergesort kein Algorithmus der das beherrscht. Das erfüllen zwar Algorithmen wie Insertion-, Bubble- und vorallem Quicksort, nur halt gerade der Mergesort nicht. Wenn du eine schnelle Implementierung dadurch erreichen möchtest, dass du nur Indizes kopierst, es geht schöner. Du kannst einfacher mit Pointern arbeiten. Ein Zeiger auf ein Record ist immer 4 Byte groß (oder anders gesagt entspricht der Registerbreite -> ist optimal). Wenn du in deinem Array nur die Zeiger auf die Datensätze sortierst, kannst du mittels Derefenzierung problemfrei auf die enthaltenen Daten zugreifen und verschiebst gleichzeitig nicht unnötig viele Daten im Speicher.
Ansonsten würde ich dir Raten auch wirklich dynamische Arrays zu verwenden und nicht die Größe auf 1000 Datensätze fest zu legen. Die kannst du einfach verwenden:

Delphi-Quellcode:

var dynArray : Array of TDeinPointer; // dyn. Array vom Typ TDeinPointer
begin
  // die Länge dyn. zuweisen (natürlich an geeigneter Stelle!)
  setLength(dynArray, right - left);  
 
  // irgendwas mit dem Array machen
  ....
  
  // aufräumen
  finalize(dynArray);
  setLength(dynArray, 0);
end;

Bei dem Irgendwas mit dem Array machen, ist es halt wichtig, dass du nicht versuchst in-place zu arbeiten. Das heißt, dein Eingabearray wird nicht direkt weiterverwendet. Dies ist wegen dem Mischen leider nicht möglich. Du mussst wirklich ein neu erzeugtes Array zurückgeben (gerade hier liegen viele Nachteile im Mergesort). Effizienter ist und bleibt da halt der Quicksort (mehr als nur im Mittel) und eigentlich müsste auch der Heapsort (weil in-place) etwas flinker sein. Aber da bin ich mir wieder nicht sicher, assymptisch laufen die alle (im MIttel) gleich.

Gruß Der Unwissende

[Coder]

leider kann ich unter Delphi 3 keine Dynamischen Arrays verwenden, da es die noch nicht gibt.
Darum habe ich das mit den Indizes versucht.

außerdem habe ich Mergesort asugewählt, weil er stabil ist .. also bei evtl. gleichen Datensätzen (gleiches Geb.-Datum) dennoch (die Namen) alphabetisch sortiert.

Gibt's noch weitere alternativen?

Aber warum kommt das Ding so durcheinander?

gibt Size sortiert aus, wenn ich nach Name sortiere....

[Der_Unwissende]

Also wenn du nach Namen sortierst, sollten die Datensätze natürlich nur nach Namen sortiert sein (unabhängig von den Geburtsdaten usw.). Stabil ist ein Sortierverfahren eigentlich nur dann, wenn die Eingabereihenfolge bei gleichen Datensätzen erhalten bleibt. Hast du also ein Feld, hier einfach mal Tupel aus einer Zahl und einem Namen und sortierst nach dem Namen, so ist ein
[(Maier, 1), (Rudi, 2), (Maier, 2)] -> [(Maier, 1), (Maier, 2), (Rudi, 2)] stabil
[(Maier, 1), (Rudi, 2), (Maier, 2)] -> [(Maier, 2), (Maier, 1), (Rudi, 2)] nicht stabil
wobei natürlich die Reihenfolge garantiert werden muss. Also hier, dass wenn der (Maier, 1) vor dem (Maier, 2) in der Eingabe steht, er es auch in der Sortierung tut.

Ich würde dir ehrlich gesagt immer noch dazu raten, deine Implementierung nochmals vor zu nehmen. Nimm wirklich besser Zeiger auf deinen Record. Dann kannst du das mit den Indizes komplett streichen.
Der Mergesort ist sehr abstrakt nur ein

Code:

MergeSort(Feld A) : Feld
begin
  wenn Länge(A) = 1 dann
    Ergebnis := A;

  sonst
    Ergebnis := Mische (MergeSort (erste Hälfte von A)) (MergeSort (zweite Hälfte von A))
end; 

Mische (Feld A, Feld B) : Feld
begin
  // ist klar
end;

Wichtig ist hier, dass dein zurück gegebenes Feld von MergeSort immer ein neu angelegtes Feld ist. Du hast eine Eingabe A, zerteilst die in zwei Felder B und C (in der Mitte), sortierst diese Felder rekursiv und gibst das sortiert-gemischte Feld D zurück. Als Feld kannst du also einfach ein Feld von Zeigern auf deine Datensätze verwenden. Dann sortierst du die Pointer (nur 4 Byte), hast aber zum Sortieren die Daten hinter den Pointern zur Verfügung (nur bewegst du diese Daten nie im Speicher).

Hoffe ist etwas klarer. Sorry, hab deine Idee mit dem Indexverschieben zwar (denke ich) verstanden, denke aber dass es überflüssig und fehleranfällig ist (weswegen ich dort nicht nach Fehlern schauen möchte). Zudem greifst du irgendwie (soweit es ein kurzer Blick mir zeigt) auf dein eigentliches Eingabefeld zu. Und dass darf halt nicht sein. Du darfst nicht im eigentlichen Eingabefeld mischen.
Du merkst dir deine Teilfelder ja etwas virtuell (Start und Endindex). Ich versuch es mal zu visualisieren.

Eingabe : [1,2,3,1,2]

StartIndex : S, Endindex E

Teilfelder (nach ein paar Aufrufen) :
[1,2,3] [1,2] <- -> [1,2,3,1,2]
S E S E // hier jetzt dein Rechts, Links dass du dir merkst.
Jetzt mischt und sortierst du also:
Eingabefeld:
[1, 2, 3, 1, 2]
S E S E // das erste Element ist sortiert, du betrachtest nun die zwei ersten unsortierten
[1, 1, 3, 2]
S E SE // ups, jetzt hast du dein Problem, du überschreibst dir einen Wert (Stelle 2 in der Eingabe) wenn du nur mit einem Index arbeitest.

Hoffe du siehst grob was ich meine. Deshalb kannst du halt nicht in-place sortieren. Also musst du ein eigenes Array zur Rückgabe verwenden und kannst nicht nur über die Indizes gehen (dass klappt z.B. mit Quicksort oder Bubblesort, die in-place sortieren).

[Amateurprofi]

@Coder

der z.Z. in Wikipedia abgebildete MergeSort ist fehlerhaft - liefert keine stabile Sortierung.

Delphi-Quellcode:

    for z := links to rechts do 
    begin 
      if hilfs[x] < hilfs[y] then

wenn du in der Zeile unter dem begin die if-Bedingung so änderst, dann arbeitet er korrekt

     if (x<=mid) and (hilfs[x] <= hilfs[j]) then

[stoxx]

das ist leider ein grausames Beispiel, wie man überhaupt nicht programmieren sollte !
Am besten gleich wieder löschen ! Sorry ! tut mir leid, nimms nicht persönlich !
Aber wäre nicht gut, wenn das zufällig ein Anfänger als Beispiel rannehmen möchte.

Deine proceudre MergeSort_String greift auf Form1 zu, obwohl sie keine Methode von Form1 ist !!
Müll hoch 3. Gewöhn Dir sowas gar nicht erst an, Du kommst in Teufels Küche.
hol Dir mal verschiedene Bücher ("Antipatterns" von William J.Brown, Raphael C. Malveau) oder "Code Complete" von Steve McConnell)
Leider sieht man sowas hier in der DP sehr häufig.
Trenne bitte in Zukunft die Funktionalität des Programms von der Anzeige der Daten.
Das wichtigste Stichwort zum googeln dürfte für Dich das MVC Modell sein.

http://de.wikipedia.org/wiki/Model_View_Controller

Modell und view immer trennen ! Gerade bei solchen Sachen wie Sortierung von Daten, wie Du es hier gemacht hast.
Bitte sowas nicht als "gutes" Beispiel posten.
Gut gemeint ist leider nicht gut gemacht !


Findest Du Deine Procedure BubbleSortClick übersichtlich ?

i := Index[Was]; wer was wo ? was ist was ? Index ? welcher Index ? Was soll man mit diesem Quelltext lernen können ?

Bitte nicht persönlich nehmen, ja ? Ich hab auch so angefangen, leider !
Ist wirklich nur ein guter Rat !