Quicksort-Rätsel

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

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

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?

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