Problem mit Quicksort-Implementierung

[Shimau]

Ich hab hier einen Quicksort, der eigentlich abwärts sortieren soll (also größten zahlen oben/kleinster Index und kleinsten unten/größter Index). Nun treten in der Ausgabe entweder wiederholt die selben zahlen auf oder wiederholt 0. Ich hab keine Ahnung warum.

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;
  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
      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;

Bin für jeden Hinweis dankbar

[Satty67]

Darf es auch die rekursive Variante sein, die finde ich übersichtlicher. Die Stellen mit Operatoren, die für aufsteigend/absteigend gedreht werden müssen, beschränkt sich da auf zwei Stück

Delphi-Quellcode:

procedure QuickSort(var A: array of Integer);

  procedure QSort(LoIndex, HiIndex: Integer);
  var
    Lo, Hi: Integer;
    Pivot: Integer;
    Swap: Integer;
  begin
    Pivot := A[(LoIndex + HiIndex) div 2];
    Lo := LoIndex;
    Hi := HiIndex;

    repeat
      while A[Lo] < Pivot do Inc(Lo); // Hier Operator drehen
      while A[Hi] > Pivot do Dec(Hi); // Hier auch
      if Lo <= Hi then
      begin
        if Lo < Hi then
        begin
          Swap := A[Lo];
          A[Lo] := A[Hi];
          A[Hi] := Swap;
        end;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;

    if LoIndex < Hi then QSort(LoIndex, Hi);
    if Lo < HiIndex then QSort(Lo, HiIndex);
  end;

begin
  QSort(Low(A), High(A));
end;

Ansonsten:

bei Deiner Version müsstest Du prüfen, ob Du (zum original Code) die Operatoren auch nur dort gedreht hast, wo Werte verglichen werden. Dort wo der Index verglichen wird, muss der Operator gleich bleiben.

[Shimau]

mmh, müsste eigentlich so stimmen, deswegen wunder ich mich ja auch so, es treten ja Werte auf die überhaupt nicht eingegeben wurden. Und was ist mit "Stack-Überlauf" (manchmal tritt diese Fehlermeldung auf) gemeint?

[Satty67]

Also Deine Version scheint irgendwie ein Zwitter aus rekursiver und nicht rekursiver Version zu sein. Ich kenne nicht alle Varianten von QuickSort.

Stack-Überlauf lässt auf einen endlosen rekursiven Aufruf schließen oder eine zu große lokale Variable bei rekursiven Aufrufen (tippe bei Dir auf ersteres).

Das Du annimmst, dass Dein Code eigentlich richtig sein müsste, obwohl sporadische Fehler auftreten, Werte auftauchen die nie in der Liste waren und auch nicht richtig sortiert wird, finde ich zwar eine gute selbstbewusste Einstellung... aber... weist schon ;)

PS: Sehe gerade, ist wohl die kombinierte QuickSort/InsertionSort Version von Daniel... die Variante kenne ich auch anders und bringt auch nur was, wenn der Zugriff langsam ist (und natürlich wenn Sie fehlerfrei ist). Die hab' ich übrigens auch nicht zum laufen gebracht, weshalb ich den Insertion Teil anders implementiert hatte.

[Shimau]

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.

[Shimau]

Zitat:

Zitat von Satty67

PS: Sehe gerade, ist wohl die kombinierte QuickSort/InsertionSort Version von Daniel... die Variante kenne ich auch anders und bringt auch nur was, wenn der Zugriff langsam ist (und natürlich wenn Sie fehlerfrei ist). Die hab' ich übrigens auch nicht zum laufen gebracht, weshalb ich den Insertion Teil anders implementiert hatte.

Wie hast du den Insertion-Teil anders implemntiert? Glaubst du, dass es daran liegt?

[Satty67]

Ja, glaube Daniel hat da irgendwie mitten drin aufgehört.

mein QuickInsertSort für IntArrays sieht so aus:

Delphi-Quellcode:

procedure SortIntArray(A: Array of Integer);

  procedure QuickInsertSort(L,R: Integer);
  var
    I, J : integer;
    S, P : Integer;
  begin
    // QuickSort für Elemente, die weiter auseinander liegen
    if (R - L) > 25 then begin

      i := l;
      j := r;
      p := A[(l+r) DIV 2];

      repeat
        while A[i] < p do i := i + 1;
        while A[j] > p do j := j - 1;

        if i <= j then begin
          if i < j then begin
            s := A[i];
            A[i] := A[j];
            A[j] := s;
          end;
          i := i + 1;
          j := j - 1;
        end;
      until i > j;

      if l < j then QuickInsertSort(l, j);
      if i < r then QuickInsertSort(i, r);

    // InsertionSort für Element-Entfernungen <= 25
    end else begin

      for I := L + 1 to R do begin
        if (A[I] < A[I - 1]) then
        begin
          S := A[I];
          J := I;
          while ((J > L) and (A[J - 1] > S)) do
          begin
            A[J] := A[J - 1];
            J := J - 1;
          end;
          A[J] := S;
        end;
      end;

    end;
  end;

begin
  QuickInsertSort(Low(A), High(A));
end;

War für StringListen, hab es schnell umgeschrieben und hoffentlich kein Fehler eingebaut. Zumindest sieht man bei mir genau, wo welches Sortierverfahren angewendet wird.

Aber bedenke, dass ein Speicherarray ja keine unterschiedlichen Zugriffszeiten für weiter auseinander liegende Speicheradressen hat. Der Vorteil ist da nur noch minimal und kommt erst richtig zum tragen, wenn man z.B. über eine Datei sortiert..

PS: Den Wert 25 kannst Du anpassen, je langsamer der Zugriff desto größer sollte der Wert sein (so bis 200 kann was bringen)

[Shimau]

Komischerweise funktioniert bei mir der Insertionsort, aber nicht der Quicksort :gruebel: :

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.

[Satty67]

Also tut mir Leid, gegenüber Daniels Code sehe ich bei Dir keine Fehler. Operatoren wurden für absteigende Sortierfolge an den richtigen Stellen getauscht. Bleibt die Tatsache, das der Code bei mir auch noch nie funktioniert hat.

Den Code von Daniel hatte ich mir schon mal vorgenommen und bin dann zur Überzeugung gelangt, das es ein iteratives Quicksort werden sollte und Teile des rekursiven Codes mit drin ist. Ich hab' dann abgebrochen, weil ich den Faden verloren hatte. Ich bin bei solchen Analysen nicht besonders gut.

Vielleicht suchst Du im Netz nach einer iterativen Quicksort Version und vergleichst da mal, wenn sonst keine einen Vorschlag hat, wo der Fehler sein könnte.

[Shimau]

Wer jetzt noch eine Lösung für das Problem findet, bitte ich mir eine Nachricht zu senden.
Ich verwend jetzt erstmal nur den Insertionsort.