Quicksort-Rätsel

[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 von striderx:

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 von Namenloser:

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 von striderx:

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 von Dejan Vu:

Zitat von Namenloser:

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: