Fehler bei übertragen meiner Daten auf den Quicksort Code

[idefix]

Hallo!

Ich programmiere ein Vokabelprogramm.

Um die Datensätze sortieren zu können, versuche ich mich an dem Sortieralgorithmus Quicksort.
Das ist wohl schneller als andere Sortieralgorithmen?

Ich brauche was schnelles, da ich 7344 Vokabeln gespeichert habe.
Eine selbstgeschriebene Procedure dauerte schon bei 50 Vokabeln endlos.

Daher Quicksort:

http://www.delphi-treff.de/tipps/algori ... quicksort/
Das läuft auch.

Das Problem ist, meine Datenstruktur dort einzubinden.

Code: Alles auswählen

procedure Quick_Sort(var Daten[i].Phase: array of Integer; iLo, iHi: Integer);

Der Debugger steigt hier im interface-Bereich mit folgender Fehlermeldung aus:
Fatal: Syntax Error, ")" expected but "[" found.

Im implementation-Bereich konnte ich die Procedure Quicksort daher noch nicht anpassen.

Ich kriege das Programmieren schon irgendwie hin.
Nur bei solchen Deklarationsgeschichten komme ich nicht weiter.
Hier mein Code.

Ganz unten der Originalcode von Quicksort.

Evtl. müsste die Fragestellung heißen:
Gibt es einen Algorithmus, der noch schneller ist als Quicksort.

Code: Alles auswählen

type
  TDatensatz = record
    Fach   : String;
    Frage  : String;
    Antwort: String;
    faellig: TDate;
    Phase  : integer;
  end;
  TDatenArray = array of TDatensatz;     
 
  TForm1 = class(TForm)
    procedure Quick_Sort_ButtonClick(Sender: TObject);
    //    procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
    procedure Quick_Sort(var Daten[i].Phase: array of Integer; iLo, iHi: Integer);
 
  private
    { private declarations }
  public
    { public declarations }
  end; 
  // Original
 
  //Original
var
  Form1 : TForm1; 
 
var
  AnzahlVokabeln: integer;
  Daten: TDatenArray;
 
 
implementation
 
{$R *.lfm}

Code: Alles auswählen

procedure TForm1.Quick_Sort_ButtonClick(Sender: TObject);
var
  iLo, iHi: Integer;
  I: Integer;
begin
  for i := 0 to AnzahlVokabeln-1 do
  begin
    StringGrid1.Cells[1,i+1] := IntToStr(Daten[i].Phase);
  end;
  iLo := 1
  iHi := AnzahlVokabeln-1;
  Quick_Sort(Daten[i].Phase,iLo, iHi);
end;

Code: Alles auswählen

//procedure TForm1.Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
procedure TForm1.Quick_Sort(var Daten[i].Phase: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then Quick_Sort(A, iLo, Hi);
  if Lo < iHi then Quick_Sort(A, Lo, iHi);
 
  for i := 1 to AnzahlVokabeln -1 do
  begin
    StringGrid1.Cells[2,i] := IntToStr(A[i]);
  end;
end;

--------------------------

Hier der Original Quicksort Code:

Code: Alles auswählen

procedure QuickSort(var A: array of Integer);
 
  procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
  var
    Lo, Hi, Mid, T: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do Inc(Lo);
      while A[Hi] > Mid do Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then Quick_Sort(A, iLo, Hi);
    if Lo < iHi then Quick_Sort(A, Lo, iHi);
  end;
 
begin
  Quick_Sort(A, Low(A), High(A));
end;
 
Beispiel der Anwendung
procedure TForm1.Button1Click(Sender: TObject);
var
  arr: array[0..100] of integer;
  I: Integer;
begin
  for I:=Low(arr) to High(arr) do
    arr[I]:=Random(High(Integer));
 
  QuickSort(arr);
end;

Vielen Dank für schlaue Hilfe!

Gruß!
idefix

[corpsman]

Also meiner Meinung nach, fehlt dir hier ne gehörige Portion Grundlagen Verständnis.

Das hier hab ich mal mit KWrite zusammengeschustert, evtl hast glück und es funktioniert..

Code: Alles auswählen

procedure QuickSort(var A: TDatenArray);
 
  procedure Quick_Sort(var A: TDatenArray; iLo, iHi: Integer);
  var
    T :TDatensatz;
    Lo, Hi, Mid: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2].phase;
    repeat
      while A[Lo].phase < Mid do Inc(Lo);
      while A[Hi].phase > Mid do Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then Quick_Sort(A, iLo, Hi);
    if Lo < iHi then Quick_Sort(A, Lo, iHi);
  end;
 
begin
  Quick_Sort(A, Low(A), High(A));
end;
 
Aufruf :
 
QuickSort(Daten);

Quick_Sort ist eine Genestete Routine in QuickSort die Deklaration in TForm1 sollte raus, und du solltest nur QuickSort aufrufen.

Evtl. müsste die Fragestellung heißen:
Gibt es einen Algorithmus, der noch schneller ist als Quicksort.

Ja , z.B. BottomUpHeap Sort, der ist zumindest in der Theorie Schneller, da der Worst Case von Quicksort mit N^2 Schritten nicht auftritt. In der Praxis wird aber fast immer Quicksort Implementiert ( weil er so schön einfach ist ).

[mse]

Verschiedene Implementierungen von mergesort gibt es hier:
http://gitorious.org/mseide-msegui/msei ... yutils.pas
z.B.

Code: Alles auswählen

procedure mergesortpointer(const adata: pointer; const asize,acount: integer;
                            const acompare: sortcomparemethodty;
                            out apointerlist: pointerarty);
var
 ar1: pointerarty;
 step: integer;
 l,r,d: ppointer;
 stopl,stopr,stops: ppointer;
 source,dest: ppointer;
 int1: integer;
label
 endstep;
begin
 if acount = 0 then begin
  apointerlist:= nil;
  exit;
 end;
 allocuninitedarray(acount,sizeof(pointer),ar1);
 allocuninitedarray(acount,sizeof(pointer),apointerlist);
 for int1:= acount-1 downto 0 do begin
  apointerlist[int1]:= pchar(adata)+int1*asize;
 end;
 source:= pointer(apointerlist);
 dest:= pointer(ar1);
 step:= 1;
 while step < acount do begin
  d:= dest;
  l:= source;
 {$ifdef FPC}
  r:= source+step;
 {$else}
  r:= pointer(pchar(source)+step*sizeof(source^));
 {$endif}
  stopl:= r;
 {$ifdef FPC}
  stopr:= r+step;
 {$else}
  stopr:= pointer(pchar(r)+step*sizeof(r^));
 {$endif}
 {$ifdef FPC}
  stops:= source + acount;
 {$else}
  stops:= pointer(pchar(source) + acount*sizeof(source^));
 {$endif}
  if pchar(stopr) > pchar(stops) then begin
   stopr:= stops;
  end;
  while true do begin //runs
   while true do begin //steps
    while acompare((l^)^,(r^)^) <= 0 do begin
                                                           //merge from left
     d^:= l^;
     inc(l);
     inc(d);
     if l = stopl then begin
      while r <> stopr do begin
       d^:= r^;   //copy rest
       inc(d);
       inc(r);
      end;
      goto endstep;
     end;
    end;
    while acompare((l^)^,(r^)^) > 0 do begin
                                                         //merge from right;
     d^:= r^;
     inc(r);
     inc(d);
     if r = stopr then begin
      while l <> stopl do begin
       d^:= l^;   //copy rest
       inc(d);
       inc(l);
      end;
      goto endstep;
     end; 
    end;
   end;
endstep:
   if stopr = stops then begin
    break;  //run finished
   end;
   l:= stopr; //next step
  {$ifdef FPC}
   r:= l + step;
  {$else}
   r:= pointer(pchar(l) + step*sizeof(l^));
  {$endif}
   if pchar(r) >= pchar(stops) then begin
  {$ifdef FPC}
    r:= stops-1;
  {$else}
    r:= pointer(pchar(stops)-1*sizeof(stops^));
  {$endif}
   end;
   if r = l then begin
    d^:= l^;
    break;
   end;
   stopl:= r;
  {$ifdef FPC}
   stopr:= r + step;
  {$else}
   stopr:= pointer(pchar(r) + step*sizeof(r^));
  {$endif}
   if pchar(stopr) > pchar(stops) then begin
    stopr:= stops;
   end;
  end;
  d:= source;     //swap buffer
  source:= dest;
  dest:= d;
  step:= step*2;
 end;
 
 if source <> pointer(apointerlist) then begin
  apointerlist:= ar1;
 end;
end;

Martin

[Eclipticon]

Hi,

Code: Alles auswählen

procedure Quick_Sort(var Daten[i].Phase: array of Integer; iLo, iHi: Integer);

Der Debugger steigt hier im interface-Bereich mit folgender Fehlermeldung aus:
Fatal: Syntax Error, ")" expected but "[" found.

um noch auf dein urspruengliches Problem zu antworten:

Du versuchst hier in der Deklaration schon deine Daten, also die Variable die sortiert werden soll, zu uebergeben ... das darfst aber erst beim Aufruf der Prozedur machen!

In der Deklaration verwendest Du irgendeine abstrakte Variable, die halt dann im Implementation-Teil deine Daten repraesentiert. Also bleib einfach bei "A" fuer das array of integer und es sollte funktionieren ...

Alles klar?

[idefix]

Hallo!

Vielen Dank erst mal!

Ich komme erst nächstes Wochenende dazu weiter zu probieren.

Gruß!
idefix

[mse]

Hier http://gitorious.org/mseide-msegui/msei ... yutils.pas gibt es auch eine Routine zum sortieren dynamischer Arrays mittels mergesort. Um dein TDatenArray nach Phase zu sortieren:

Code: Alles auswählen

type
  TDatensatz = record
    Fach   : String;
    Frage  : String;
    Antwort: String;
    faellig: TDate;
    Phase  : integer;
  end;
  TDatenArray = array of TDatensatz;     
 
function comparephase(const leftvalue,rightvalue): integer;
begin
 result:= TDatensatz(leftvalue).Phase - TDatensatz(rightvalue).phase; 
end;
 
var
 datenarray: TDatenArray;
 
procedure tmain2fo.sortexe(const sender: TObject);
begin
 sortarray(datenarray,sizeof(tdatensatz),@comparephase);
end;

Das Sortieren von 1'000'000 Datensätzen dauert etwa eine Sekunde.

Martin