Quicksort-Rätsel

[Namenloser]

Zitat von striderx:

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:

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.