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.

[Apollonius]

Dein Dreieckstausch sieht... interessant :mrgreen: aus.

[alzaimar]

ACHTUNG! Hier kommt ein versteckter Hinweis!

Zitat:

Zitat von Apollonius

Dein Dreieckstausch sieht... interessant :mrgreen: aus.

Das war der versteckte Hinweis.

[Satty67]

Ach Du lieber Gott :oops:

Wenn zwei den Wald vor lauter Bäumen nicht sehen, sind dann beide dadurch entschuldigt, dass Sie zu zweit waren?

Bei Daniels Code fehlte damals der Insertion-Aufruf, weshalb der bei mir auch nicht funktionierte

[quendolineDD]

Ist mir beim ersten drüber blicken auch gar nicht aufgefallen :D
Aber bei Wikipedia sieht der Pseudocode wesentlich schlanker aus, als diese Implementierung von QuickSort.

[Satty67]

Ich hatte ihm ja meinen Code angeboten, da ist der QuickSort Teil kleiner und Insertion gleich. Zudem ist er auch noch 10% schneller, aber er will seinen Code zum Laufen bringen, was ich verstehen kann.

Das er im Zweifel aber nur Insertion genommen hätte, statt meinen, hat mich doch erschreckt ;)

[alzaimar]

Satty67,

wäre es Dir möglich, eine kleine Applikation zu schreiben, die die Performanceunterschiede zwischen dem generischen Quicksort und der Variante mit InsertionSort belegt? Ich meine mich zu erinnern, das eine schlanke QS-Implementierung mittlerweile (und Aufgrund optimierender Compiler und CPU Code-Cache) nicht mehr langsameer ist. Da man darüber nicht diskutieren muss, sondern Fakten sprechen lassen kann, wäre es wirklich toll, wenn Du das belegen könntest. Eine iterative Variante des QS sollte zudem auch schneller sein, aber das ließe sich -ein geeignetes kleines Testframework vorausgesetzt- sicherlich belegen/widerlegen.

[Satty67]

Hallo alzaimar,

sowas hab' ich sogar schon geschrieben... Also eine Plattform, mit der ich InsertSort und Quicksort teste bzw. Varianten davon und Kombinationen incl. Kontrollausgabe ob auch richtig sortiert wird. Ist noch ein Überbleibsel aus dem letzten Marathon, bei dem ich mich der SkipList geschlagen geben musste ;)

Ich werd' das heute nach der Arbeit etwas überarbeiten, im jetzigen Zustand möchte ich den Code niemandem zumuten. Ich lagere am besten jede Sortier-Routine in eine Extra Unit aus und poste dann heute Abend die Testplattform.

[user0815]

Habe hierzu diesen netten Link gefunden: http://www.stefan-baur.de/cs.algo.insertionsort.html
hmm, besser diesen wegen der Übersicht: http://www.stefan-baur.de/cs.algo.sort.html

[Satty67]

Ok, hab' mein Chaos-Projekt zum Testen von Sortierverfahren "etwas" aufgeräumt und die Sorter in Units ausgelagert. Sollte so nicht schwer sein, einen eigenen Sorter zum Vergleichen zu implementieren.

Ich will kein Gemecker, wegen der Programmierung, das war vorher noch wesentlich chaotischer, jetzt geht das etwas.

Drin sind BubbleSort, SelectionSort, QuickSort (Rekursiv) aus dem Thread-Beispiel von Delphi und InsertSort. Wobei ich bei QuickSort einen unnötigen Swap noch umgangen hab. Zusätzlich noch QuickInsertSort, das aber bei Speicher-Sortieren seine Vorteile nicht ausspielen kann und QuickSort (Iterativ), wobei ich etwas Probleme beim umsetzten des Codes hatte. Für Strings musste ich eine zusätzliche Prüfung einbauen.

Wer will, kann seinen Code einbauen und Testen oder das ganze auf Dateien anwenden, um z.B. die Vorteile von QuickInsertSort zu testen.

PS: Die Exe ist mit dabei und wer FastMM4 nicht verwendet, einfach aus der Deklaration rauswerfen.

PPS: Schwer es genau zu sagen, aber man sieht eine Tendenz. QuickInsertSort ist beim Sortieren von Speicherlisten sogar minimal langsamer. Überhaupt spricht bei der Performance von Quicksort nichts dagegen, für Speicherlisten nur QuickSort zu nehmen. Für Dateien ist die SkipListe besser, die beim Speichersortieren wohl wegen kompletten Kopieren der Liste ein Putt liefert.

Ergebnisse:

Code:

_358 ms für 10.000 Int64-Elemente mit Bubble-Sort
_214 ms für 10.000 Int64-Elemente mit Selection-Sort
__49 ms für 10.000 Int64-Elemente mit Insertion-Sort
___0 ms für 10.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt)
___1 ms für 10.000 Int64-Elemente mit Quick-Sort (iterativ)
___1 ms für 10.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

3770 ms für 10.000 String-Elemente mit Bubble-Sort
1389 ms für 10.000 String-Elemente mit Selection-Sort
1068 ms für 10.000 String-Elemente mit Insertion-Sort
___5 ms für 10.000 String-Elemente mit Quick-Sort (rekursiv, kompakt)
___6 ms für 10.000 String-Elemente mit Quick-Sort (iterativ)
___6 ms für 10.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

_357 ms für 2.500.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt)
_370 ms für 2.500.000 Int64-Elemente mit Quick-Sort (iterativ)
_417 ms für 2.500.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

3150 ms für 2.500.000 String-Elemente mit Quick-Sort (rekursiv, kompakt)
3596 ms für 2.500.000 String-Elemente mit Quick-Sort (iterativ)
3652 ms für 2.500.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)