Quicksort-Rätsel

[striderx]

Hallo zusammen,

seit nicht wenigen Jahren setze ich Quicksort zum sortieren von Daten ein - alles problemlos. Jetzt habe ich aber einen Fall, in dem das Sortier-Ergebnis nicht korrekt ist. Wenn ich dann noch einmal sortiere stimmt es. Auch wenn ich alternativ einen Insertion-Sort nehme, klappt es - d. h. an der Vergleichsfunktion ('Less', s. u.) scheint es also nicht zu liegen.

Kann mir bitte jemand das Brett vor em Kopf wegnehmen?



Hier der Source Code:

procedure tdlgMain.SortData;

begin
DataSort(1, TotalRecs);
end;

procedure tdlgMain.DataSort(Start, Stop: Word);

var
tStart: Word;
tStop: Word;
pTemp: rCompRec;

begin
tStart := Start;
tStop := Stop;
aData[0] := aData[(tStart + tStop) DIV 2];
repeat
while Less(tStart, 0) do Inc(tStart);
while Less(0, tStop) do Dec(tStop);
if tStart <= tStop then begin
pTemp := aData[tStart];
aData[tStart] := aData[tStop];
aData[tStop] := pTemp;
Inc(tStart);
Dec(tStop);
end;
until tStart > tStop;
if Start < tStop then DataSort(Start, tStop);
if tStart < Stop then DataSort(tStart, Stop);
end;

[Sir Rufo]

Warum keine Delphi-Tags um den Code und warum nicht die eingebaute Sortierfunktion? :gruebel:

[striderx]

>>Warum keine Delphi-Tags<<

Und was wäre das genau?

>>warum nicht die eingebaute Sortierfunktion<<

Weil es das Problem dort nicht zu liegen scheint - denn beim Insertion-Sort gibt es damit kein Problem. Aber wenn ich weiß, was die Delphi-Tags sind, liefere ich die gerne nach.

[Sir Rufo]

Die Delphi-Tags sind dazu da, dass wir hier keinen Augenkrebs bekommen, wenn wir uns Delphi-Code ansehen müssen.

Statt

procedure foo( bar : string );
begin
writeln( bar );
end;

schreibt man in den Editor

Code:

[DELPHI]
procedure foo( bar : string );
begin
  writeln( bar );
end;
[/DELPHI]

und heraus kommt

Delphi-Quellcode:

procedure foo( bar : string );
begin
  writeln( bar );
end;

[p80286]

Zitat:

Zitat von striderx (Beitrag 1279482)

>>Warum keine Delphi-Tags<<

Und was wäre das genau?

Nimm den "GriechenHelm"

>>warum nicht die eingebaute Sortierfunktion<<

Zitat:

Zitat von striderx (Beitrag 1279482)

Weil es das Problem dort nicht zu liegen scheint - denn beim Insertion-Sort gibt es damit kein Problem.

Die Logik versteh ich jetzt nicht!
Was heißt eigentlich "korrekt"? Dir ist schon klar, daß Quicksort kein stabiles Verfahren ist?

Gruß
K-H

[striderx]

Dann auf ein Neues:

Delphi-Quellcode:

procedure tdlgMain.SortData;

begin
  DataSort(1, TotalRecs);
end;

procedure tdlgMain.DataSort(Start, Stop:  Word);

var
  pTemp:   rCompRec;
  tStart:  Word;
  tStop:   Word;

begin
  tStart   := Start;
  tStop    := Stop;
  aData[0] := aData[(tStart + tStop) DIV 2];
  repeat
    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop)  do Dec(tStop);
    if tStart <= tStop then begin
       pTemp         := aData[tStart];
       aData[tStart] := aData[tStop];
       aData[tStop]  := pTemp;
       Inc(tStart);
       Dec(tStop);
    end;
  until tStart > tStop;
  if Start  < tStop then DataSort(Start, tStop);
  if tStart < Stop then DataSort(tStart, Stop);
end;

function tdlgMain.Less(X, Y:  Word):  Boolean;

var
  R:   Integer;
  S1:  String;
  S2:  String;

begin
  if (aData[X].Deleted = False) and (aData[Y].Deleted = True) then begin
     Result := True;
     Exit;
  end
  else if (aData[X].Deleted = True) and (aData[Y].Deleted = False) then begin
     Result := False;
     Exit;
  end;
  if (aData[X].RecType) < (aData[Y].RecType) then begin
     Result := True;
     Exit;
  end
  else if (aData[X].RecType) > (aData[Y].RecType) then begin
     Result := False;
     Exit;
  end;
  Result := False;
  case aData[X].RecType of
     1: begin                                                                   
          S1 := GetArtistSurname(aData[X].wlIndexArtist);
          S2 := GetArtistSurname(aData[Y].wlIndexArtist);
          R  := AnsiCompareText(S1, S2);
          if  R < 0 then Result := True
          else if R = 0 then begin
             S1 := GetArtistFirstName(aData[X].wlIndexArtist);
             S2 := GetArtistFirstName(aData[Y].wlIndexArtist);
             R  := AnsiCompareText(S1, S2);
             if  R < 0 then Result := True
             else if R = 0 then begin
                S1 := aData[X].wlNameofWork;
                S2 := aData[Y].wlNameofWork;
                if AnsiCompareText(S1, S2) < 0 then Result := True
             end;
          end;
        end;
     2: begin                                                                   
          S1 := aData[X].arSurname;
          S2 := aData[Y].arSurname;
          R  := AnsiCompareText(S1, S2);
          if  R < 0 then Result := True
          else if R = 0 then begin
             S1 := aData[X].arFirstName;
             S2 := aData[Y].arFirstName;
             if AnsiCompareText(S1, S2) < 0 then Result := True
          end;
        end;
     3: begin                                                                   
          if (aData[X].hoDate <> 0) and (aData[Y].hoDate = 0)
             then Result := True
          else if (aData[X].hoDate = 0) and (aData[Y].hoDate <> 0)
             then Result := False
          else if (aData[X].hoDate = 0) and (aData[Y].hoDate = 0)then begin
                if aData[X].hoIndexHolidays < aData[Y].hoIndexHolidays
                   then result := True;
          end
          else if aData[X].hoDate < aData[Y].hoDate then Result := True;
        end;
     4: begin                                                                   
          S1 := aData[X].cuSurname;
          S2 := aData[Y].cuSurname;
          R  := AnsiCompareText(S1, S2);
          if  R < 0 then Result := True
          else if R = 0 then begin
             S1 := aData[X].cuFirstName;
             S2 := aData[Y].cuFirstName;
             if AnsiCompareText(S1, S2) < 0 then Result := True
          end;
        end;
     5: begin                                                                   
          S1 := aData[X].saArticle;
          S2 := aData[Y].saArticle;
          if AnsiCompareText(S1, S2) < 0 then Result := True
        end;
     6: if aData[X].prIndexPrices < aData[Y].prIndexPrices then Result := True; 
     7: begin                                                                   
          S1 := aData[X].emSurname;
          S2 := aData[Y].emSurname;
          R  := AnsiCompareText(S1, S2);
          if  R < 0 then Result := True
          else if R = 0 then begin
             S1 := aData[X].emFirstName;
             S2 := aData[Y].emFirstName;
             if AnsiCompareText(S1, S2) < 0 then Result := True
          end;
        end;
  end;
end;

[Sir Rufo]

Also ich weiß ja nicht was du da wirklich produzieren und du dich so quälen möchtest, denn eigentlich brauchst du dir nur ein paar Comparer zu erzeugen und jagst diese dann über das Array TArray.Sort<T> oder über eine Liste TList<T>.Sort.

Als Sortier-Algorithmus wird dort ein QuickSort verwendet, du kannst, wenn du möchtest auch einen eigenen Sortier-Algorithmus verwenden, allerdings würde ich dazu auch immer den IComparer<T> verwenden.

[striderx]

Hallo Sir Rufo,

danke für Deine Hinweise. Meine Anwendung nutzt ein Datenmodell mit varianten Records - deswegen die Unterscheidung per Record-Typ. Und je nach Typ wird nach unterschiedlichen Feldern sortiert. Ich kenne mich mit IComparer jetzt nicht aus, aber so auf den ersten Blick scheint mir das auf diese Situation nicht zu passen.

Wie dem auch sei: Meine Frage ist nach wie vor, warum der bewährte Quicksort-Algorhythmus hier nicht funktioniert bzw. erst nach dem zweiten Sortierlauf. Derzeit helfe ich mir mit einem Insertion-Sort, der es beim ersten Mal richtig macht und hier auch nicht zu langsam ist, weil die Daten schon weitgehend vorsortiert sind.

[striderx]

@p80286

sorry, habe Deine Antwort erst jetzt gesehen.

>>Die Logik versteh ich jetzt nicht!<<

Die Vergleichsfunktion produziert beim Insertion-Sort das korrekte Ergebnis. Korrekt bedeutet, dass die Reihenfolge alphabetisch aufsteigend ist.

>>Dir ist schon klar, daß Quicksort kein stabiles Verfahren ist?<<

Ich habe instabil bislang so verstanden, dass Elemente mit selbem SortierSchlüssel ihre Originalreihenfolge nicht behalten. Bei mir steht aber z. B. Meier vor Ahlenfeld.

[Namenloser]

Zitat:

Zitat von striderx (Beitrag 1279498)

Delphi-Quellcode:

case aData[X].RecType of

Bist du sicher, dass RecType einen der Werte hat, die du im Case behandelst? Möglicherweise tritt keiner der Fälle dort ein, sodass für alle Vergleiche False zurückgeliefert wird. Da QuickSort kein stabiles Verfahren ist, werden dabei die Einträge durcheinandergewirbelt.

[striderx]

Ja, da bin ich sicher.

Und: Mit dem Insertion-Sort, der ja dieselbe Vergleichs-Funktion benutzt, klappt es ohne Probleme.

[Namenloser]

Hmm, okay, auf den zweiten Blick:

Delphi-Quellcode:

    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);

Fehlt da nicht jeweils eine Abbruchbedingung gegen das Überschreiten der Array-Grenzen?

Edit: Außerdem:

Delphi-Quellcode:

aData[0] := aData[(tStart + tStop) DIV 2];

Da wird das erste Element ja einfach überschrieben. Wenn dann müsstest du die beiden Elemente vertauschen. Oder du lässt dieses Implementierungsdetail einfach weg und speicherst das Pivot-Element in einer lokalen Variable zwischen.

[Uwe Raabe]

Zitat:

Zitat von Namenloser (Beitrag 1279547)

Hmm, okay, auf den zweiten Blick:

Delphi-Quellcode:

    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);

Fehlt da nicht jeweils eine Abbruchbedingung gegen das Überschreiten der Array-Grenzen?

Edit: Außerdem:

Delphi-Quellcode:

aData[0] := aData[(tStart + tStop) DIV 2];

Da wird das erste Element ja einfach überschrieben. Wenn dann müsstest du die beiden Elemente vertauschen. Oder du lässt dieses Implementierungsdetail einfach weg und speicherst das Pivot-Element in einer lokalen Variable zwischen.

Ist zwar mächtig unsauber, aber das 0-Element wird offensichtlich nicht benutzt. Aus diesem Grund sollte auch die Abbruchbedingung erfüllt sein, da in dem 0-Element das Pivot-Element steht, und spätestens wenn die Schleife diese erreicht, bricht sie ab.

[Namenloser]

Das gilt aber nur für die eine Richtung, oder? :gruebel:

Und überhaupt: Fehlt da nicht irgendwie das „Herz“ von Quicksort, nämlich, dass die Elemente, die kleiner sind als das Pivot-Element, auf die eine Seite und alle anderen Elemente auf die andere Seite gepackt werden? Je länger ich auf diesen Code draufschaue, desto unklarer wird er mir.

[striderx]

>>Fehlt da nicht irgendwie das „Herz“ von Quicksort ...<<

Das passiert m. E. hier:

Delphi-Quellcode:

    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop)  do Dec(tStop);

Mit der 0 wird der Pivot-Record referenziert, der in dem Array-Element 0 enthalten ist.

[striderx]

Ich habe den Fehler gefunden - wie so oft lag er dort, wo man am wenigsten sucht:

Schuld war der Rückgabewert der Funktion 'GetArtistSurname', welche nicht alle Datensätze bis zum Ende durchlaufen und daher in einigen Fällen einen leeren String zurückgegeben hat.


Vielen Dank für Eure Bemühungen, das Brett vor meinem Kopf zu entfernen!!!

[Namenloser]

Zitat:

Zitat von striderx (Beitrag 1279554)

Das passiert m. E. hier:

Delphi-Quellcode:

    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop)  do Dec(tStop);

Okay, mag sein. Ich gebe zu, ich habe mir diese „iterative“ Quicksort-Variante bisher nie so genau angeschaut, weil ich das schon immer etwas verwirrend fand.

Wie auch immer, freut mich, dass du den Fehler trotzdem gefunden hast.

[Dejan Vu]

Zitat:

Zitat von Namenloser (Beitrag 1279559)

Ich gebe zu, ich habe mir diese „iterative“ Quicksort-Variante bisher nie so genau angeschaut, weil ich das schon immer etwas verwirrend fand.

Das ist keine iterative Quicksort-Variante, sondern die einfachste, nämlich die Rekursive. Die iterative Quicksort-Variante, die ich kenne, ersetzt den rekursiven Aufruf durch einen Stack, der die Indizes der zu sortierenden Teilarrays enthält.

[striderx]

Nachtrag:

Warum der Insertion Sort aber trotz der fehlerhaften Funktion das richtige Ergebnis liefert, habe ich bislang noch nicht verstanden:

Delphi-Quellcode:

procedure tdlgMain.SortData;

var
  I:      Word;
  J:      Word;

begin
  for I := 1 to TotalRecs do begin
      J := I;
      aData[0] := aData[I];
      while (J > 0) and (Less(0, J - 1)) do begin
        aData[J] := aData[J - 1];
        Dec(J);
      end;
      aData[J] := aData[0];
  end;
end;

Er durchläuft zwar alle Datensätze bis zum Ende, aber benutzt halt dieselbe Funktion ...

[Uwe Raabe]

Zitat:

Zitat von striderx (Beitrag 1279574)

Er durchläuft zwar alle Datensätze bis zum Ende, aber benutzt halt dieselbe Funktion ...

Allerdings werden dabei unterschiedliche Paare in unterschiedlicher Kombination verglichen. Wenn deine Less-Funktion nicht stabil ist, können die ulkigsten Dinge passieren.

[Namenloser]

Zitat:

Zitat von Dejan Vu (Beitrag 1279562)

Zitat:

Zitat von Namenloser (Beitrag 1279559)

Ich gebe zu, ich habe mir diese „iterative“ Quicksort-Variante bisher nie so genau angeschaut, weil ich das schon immer etwas verwirrend fand.

Das ist keine iterative Quicksort-Variante, sondern die einfachste, nämlich die Rekursive. Die iterative Quicksort-Variante, die ich kenne, ersetzt den rekursiven Aufruf durch einen Stack, der die Indizes der zu sortierenden Teilarrays enthält.

Ja, bin gestern wohl irgendwie mit dem falschen Fuß aufgestanden.

[Dejan Vu]

Also wenn *ich* mit dem falschen Fuß aufgestanden bin, dann ist das mein geringstes Problem (das ich mal rekursiv und iterativ verwechsle). Insofern: Ausgeglichen, dein Gemüt, würd ich mal sagen: :thumb::thumb: