Einzelnen Beitrag anzeigen

Shimau

Registriert seit: 8. Jun 2009
Ort: Leipzig
14 Beiträge
 
Delphi 7 Personal
 
#5

Re: Problem mit Quicksort-Implementierung

  Alt 10. Jun 2009, 18:11
Der Zugriff ist auch extrem langsam, nur ich wollts zum verständniss und Probe ma mit Integerwerten machen. Also ma noch was zum Algo: Es ist ein rekursiver:

Delphi-Quellcode:
Procedure TForm1.QuickSort(Anf,Ende:integer);
var i, j, p, q, k: Integer;
    tausch: integer;{für Dreieckstausch} 
    v: integer;
Begin
  i:= Anf-1;
  p:= Anf-1; //Anfangsdekl.
  j:= Ende;
  q:= Ende;
  v:= Zahlen[Ende];

    Repeat
      inc( i ); //inc~um 1 erhöhen
      While (Zahlen[i] > v) Do
      Begin
        inc( i );
      End;

      dec( j ); //dec~ um 1 vermindern //Die Schleife ist ähnlich wie bei Satty67
      While (v > Zahlen[j]) Do //nur mit Dreieckstausch statt Swap(), macht
      Begin //aber genau dasselbe
        dec( j );
        If (j < Anf) Then Break; //Break~Verlasse die Schleife
      End;

      If (i >= j) Then Break;

      Zahlen[i]:=tausch; //Dreieckstausch
      Zahlen[i]:=Zahlen[j];
      Zahlen[j]:=tausch;

      If (Zahlen[i] = v) Then
      Begin
        inc( p );
        Zahlen[i]:=tausch;
        Zahlen[i]:=Zahlen[p];
        Zahlen[p]:=tausch;
      End;

      If (Zahlen[j] = v) Then
      Begin
        dec( q );
        Zahlen[q]:=tausch;
        Zahlen[q]:=Zahlen[j];
        Zahlen[j]:=tausch;
      End;
    until (j < i);

    Zahlen[i]:=tausch;
    Zahlen[i]:=Zahlen[Ende];
    Zahlen[Ende]:=tausch;
    j:= i-1;
    inc( i );

    k:= Anf;
    While (k < p) Do //hier werden gleiche Werte wie der Pivot
    Begin // einfach vor/hinter den Pivot sortiert
      inc( k ); //weil man sie ja nicht mehr mitsortieren muss
      dec( j );
      Zahlen[k]:=tausch;
      Zahlen[k]:=Zahlen[j];
      Zahlen[j]:=tausch;
    End;

    k:= Ende-1;
    While (k > q) Do
    Begin
      dec( k );
      inc( i );
      Zahlen[i]:=tausch;
      Zahlen[i]:=Zahlen[k];
      Zahlen[k]:=tausch;
    End;

    QuickSort( Anf, j); //Aufspaltung 2 Teilmengen, Rekursion
    QuickSort( i, Ende);
  End;
PS: Und ich meinte mit ich glaub dass es stimmt die Vergleichsoperatoren und wollte ausdrücklen, dass ich nciht mehr weiter weiss.
  Mit Zitat antworten Zitat