Einzelnen Beitrag anzeigen

Benutzerbild von Coder
Coder

Registriert seit: 27. Feb 2004
Ort: Bochum
206 Beiträge
 
Delphi 3 Professional
 
#1

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

  Alt 25. Jun 2006, 11:42
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.
ICQ: 204141443
Delphi 3 Professional, Intel 2x 2,4Ghz, 3 GB-Graka, Sound-onBrd, --
außerdem D2S, D3Pro, D4S, D5S, D6S, D7S + Indy, Lazarus, VB5Std, VC++5Pro, Tasm4+5 - was braucht man mehr?
-
  Mit Zitat antworten Zitat