Probleme mit Quicksort

[Christian Marquardt]

Ich möchte eine TStringList sortieren. Die eingebaute sort-Methode ist nicht ausreichend, da, sie nur Strings sortiert (nummerisch oder nach Datum ist schlecht.)

Zu diesem Zweck habe ich mir von

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm

den Quicksort-Algorithmus besorgt und diesen wie folgt angepasst, so dass zum sortieren eine Funktion (hier SortProc) aufgerufen wird, die die TStringListe (hier sortreihe) dann nach verschiedenen Kriterien sortieren kann. Bei nur wenigen Einträgen klappt das auch. Jedoch treten bei mehreren Einträgen Fehler auf (siehe folgende Grafiken):

Hier der Code, der den Quicksort durchführen soll (also die Teilung & Rekursion):

<pre>
void TExtendedStringGrid::Sort(int lo, int hi)
{
//Quicksort
int i=lo,j=hi,t;
int x=(lo+hi)/2;
while(i<=j)
{
t=SortProc(i,x);
while(t<0)
{
i++;
t=SortProc(i,x);
}
t=SortProc(j,x);
while(t>0)
{
j--;
t=SortProc(j,x);
}
if(i<=j)
{
sortreihe->Exchange(i,j);
i++;
j--;
}
}
if(lo<j)
Sort(lo,j);
if(i<hi)
Sort(i,hi);
}

</pre>

Hier die Grafik mit der Ausgangssituation und der Situation nach dem sortieren:

<IMG
SRC="home.snafu.de/christian.marquardt/links.7/gfx.7/bild1,jpg" BORDER="0" ALIGN="LEFT"><IMG
SRC="home.snafu.de/christian.marquardt/links.7/gfx.7/bild1,jpg" BORDER="0">

Woran liegt das schlechte Sortier-Ergebnis??

Danke

Christian

[Christian Marquardt]

Die Grafiken sind hier (grrr vertippt und man kommt nicht mehr ran):

http://home.snafu.de/christian.marquardt/links.7/gfx.7/bild1.jpg

http://home.snafu.de/christian.marquardt/links.7/gfx.7/bild2.jp

[Christian Marquardt]

Den Fehler gefunden (wenns interessiert):

hier

int x=(lo+hi)/2;

wird der Index genommen, aber als Mittelwert muss man sich den Inhalt merken

[Ulrich Gerhardt]

Dumme Frage: TStringList.CustomSort tut's wohl nicht?
<br>Uli

[Christian Marquardt]

Nein, leider läßt die in CustomSort

(CALLBACK *TStringListSortCompare)(TStringList* List, int Index1, int Index2);

erwartet CALLBACK Funktion TStringListSortCompare

nicht als Klassenmethode implementieren.

Dazu gab es hier von mir schon eine Frage:

<a href="/webx?50@@.ee8daef">Christian Marquardt "TStringList und CustomSort" 29.12.2002 09:22</a&gt

[Ulrich Gerhardt]

&gt; Dazu gab es hier von mir schon eine Frage:
<br>Ich hätte es dir auch so geglaubt. :-)
<br>Einen Versuch war's wert.
<br>Uli

[Christian Marquardt]

"Ich hätte es dir auch so geglaubt. :-)"

Nööö, darum ging es nicht, sondern wenn das mit CustomSort geht wäre ich natürlich froh.

Verstehe auch nicht, warum das nicht in einer Klasse geht??

Das ganze ist eine Grid-Komponente

http://home.snafu.de/christian.marquardt/komponenten.2/2_extendedstringgrid.htm

[Ulrich Gerhardt]

&gt; Verstehe auch nicht, warum das nicht in einer Klasse geht??
<br>Schon blöd, nachdem ja sonst alles in der VCL auf Events basiert.
Notfalls hätte es ja auch noch ein Data-Pointer als viertes
Argument getan, aber gar kein Kontext ist etwas wenig.
<br>Uli

[Fred Nest]

<PRE>
Hi Christian!

Deine Callback funktion muß als
static in der Klasse deklariert
sein, damit der Compiler/Linker
die Adresse schon kennt.

static int _fastcall mySort(...)

Gruß Fred

</PRE&gt

[Fred Nest]

Sorry !

Noch was vergessen!
Wenn die Datenmenge zu groß wird,
dann wird Quicksort zu Slowsort.

Gruß Fre

[Christian Marquardt]

Danke für den Hinweis, aber auch mit static hatte ich Probleme. Eine static Methode gibt es dann nur einmal für alle Instanzen der Klasse.

Wie weiß ich dann innerhalb der static Methode welche Instanz die Methode gerade benutzt, wenn ich mit das nicht beim anlegen der instanz irgendwo merke??

Der "Hand" - Quicksort läuft jetzt :-)

[Fred Nest]

Hi Christian!<br>

Übergebe einfach den this mit.<br>
Diesen kannst Du doch abfragen.<br>
Ich mache es immer so, daß ich die<br>
zu sortierende Liste mit übergebe.<br>

Gruß Fre

[Christian Marquardt]

Grrrr, das wäre eine Idee gewesen, Danke

:-)

[Uwe Richtsteig]

Hallo, Christian!

Nachdem ich wohl von derer Seite her auf das schlechte Sortierergebnis von <b>QuickSort</b> gestossen bin (will eine Array mit <b>struct</b>-Variablen = <i>Record</i> nach beliebigen "Spalten" sortieren, ohne zuvor einen Vektor der "Sortierspalte" anzulegen), würde mich der Weg oder besser noch die Lösung, deiner Routine "Hand"-QuickSort, wenn es denn eine Programmlösung ist, interessieren.

Meine Versuche, in denen mal sortierte, mal "vor"-sortierte Listen erzeugt wurden, je nach Ausgangsdaten, sind letzlich dahin gekommen, dass ich eine "Step-by-Step" Lösung konzipiert habe, dier es mir gestattet, die Zwischenstände zu beobachten (Code kann ich gerne zum Herunterladen an am Problem interessierte zur verfügung stellen; die Einschrängung an die Nutzer muß gegeben werden, da es sich eben nur um eine speziell für die Untersuchung gebaute MyQuickSort-Form mit zugehörigen Dateien handelt).

Das mir vorliegende Problem besteht also darin, dass ein Array auf der Variablen
<pre>struct
{
"-die cpp Datei handelt mit und MyQuickSort.h prj-kein Anwendungswenn interesse . ebei bmir zufällig ma scheitern bisher Lös

[Uwe Richtsteig]

<blockquote><i>Erstfassung konnte durch falsche Tasteneingaben nicht vollständig erstellt werden.
Uwe</i></blockquote>
Nochmal von Anfang an:

Hallo, Christian!

Nachdem ich wohl von derer Seite her auf das schlechte Sortierergebnis von <b>QuickSort</b> gestossen bin (will eine Array mit <b>struct</b>-Variablen = <i>Record</i> nach beliebigen "Spalten" sortieren, ohne zuvor einen Vektor der "Sortierspalte" anzulegen), würde mich der Weg oder besser noch die Lösung, deiner Routine "Hand"-QuickSort, wenn es denn eine Programmlösung ist, interessieren.

Meine Versuche, in denen mal sortierte, mal "vor"-sortierte Listen erzeugt wurden, je nach Ausgangsdaten, sind letzlich dahin gekommen, dass ich eine "Step-by-Step" Lösung konzipiert habe, dier es mir gestattet, die Zwischenstände zu beobachten (Code kann ich gerne zum Herunterladen an am Problem interessierte zur verfügung stellen; die Einschrängung an die Nutzer muß gegeben werden, da es sich eben nur um eine speziell für die Untersuchung gebaute MyQuickSort-Form mit zugehörigen Dateien handelt).

Das mir vorliegende Problem besteht also darin, dass ein Array auf der Variablen
<pre>struct Record
{
int iSp1;
AnsiString astrSp2;
TDateTime dtSp3;
unsigned uSp4;
float fSp4;
};

class TForm1: ....
{
....
public:
void MyQuickSort(int sortcol, int links, int rechts);
Record* rec;
....
}
...</pre>

Zur Laufzeit wird unter Verwendung von maxRecEdit->Text die Feldgröße bestimmt<br>
<b>rec = new Record[StrToInt(maxRecEdit->Text)];</b>)<br>
gesetzt und, je nach weiteren Vorgaben, das Feld mit Zufallswerten gefüllt.

In der rekrusiv aufgerufenen Funktion <br><b>MyQuickSort(...){....}</b><br>
wird dann in der Abfrage-Ausdruck in<br>
<b>while( a[i] < a[l]) i++;</b> die Abfrage durch das <b>bool-return</b>-Ergebnis einer Funktion<br>
<b>bool IsLessThen(int sortcol, int v1, int v2);</b><br>
geliefert, in der über eine switch-Folge der Vergleich der Spaltewerte in den Zellen v1 und v2 durchgeführt wird (statisch gegebene vorgegebene Datentypen in Record-struct; für die Untersuchung wird die Record-struct auf ein Datenfeld vom Typ float reduziert, die mit ihrer Nachkommastellenanzahl variabel über die Eingabe gesteuert werden kann).

Meine bisherigen Auswertugnen sind noch nicht so tief gegangen, dass ich auf die Lösung für das unterschiedliche Ergebnisverhalten gestossen bin, da ich auch hoffe, im hier oder im Internet etwas über die vermeindliche Problematik zu erfahren oder dies mit Interessiert diskutieren zu können.

Zum Algorhythmus QuickSort selbt ist zu bemerken, das dieser, in eben dem allgem bekannten Aufbau, auch in den BCB-Beispiel <b>thsort</b> verwendet wird.

Ein Gedanke, für kleine Bereiche (wenn also durch die Rekrusion den Abstand zwischen <b>links</b> und <b>rechts</b> weit veringert hat) den einfachen "Doppel-Schleifen"-Algorhythmus zu benutzen, werde ich noch prüfen.

Danke für das Lesen bis hierher und Gruß!
Uw