Einzelnen Beitrag anzeigen

Shimau

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

Re: Problem mit Quicksort-Implementierung

  Alt 10. Jun 2009, 17:25
Komischerweise funktioniert bei mir der Insertionsort, aber nicht der Quicksort :

Delphi-Quellcode:
//Insertionsort
Procedure TForm1.Insertion(Anf,Ende:integer);
var i,j: Integer;
    v:integer;
Begin
  For i:= Anf+1 To Ende Do
  Begin
    v:= Zahlen[i];
    j:= i;
    While (j > Anf) and (Zahlen[j-1] < v) Do
    Begin
      Zahlen[j]:= Zahlen[j-1]; //Kleinere Elemente werden nach rechts gerückt
      dec( j );
    End;
    Zahlen[j]:= v; //dann Elemnt in Lücke einfügen
  End;
End;

//Quicksort
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;
  j:= Ende;
  q:= Ende;
  v:= Zahlen[Ende];

  If (Ende - Anf)+1 > 20 Then
  Begin
    Repeat
      inc( i ); //inc~um 1 erhöhen
      While (Zahlen[i] > v) Do
      Begin
        inc( i );
      End;

      dec( j ); //dec~ um 1 vermindern
      While (v > Zahlen[j]) Do
      Begin
        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
    Begin
      inc( k );
      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
    QuickSort( i, Ende);
  End
  else
  begin
    Insertion(Anf,Ende); //wenn <=20 Elemente Insertionsort statt Quicksort
  end;
End;
PS: Später werden statt Integer Eigenschaften von klassen sortiert, deren zugriff schon mehr an rechenaufwand erfordert als bei Integers.
  Mit Zitat antworten Zitat