Diskussion über /Implementation

Schon mal gründlich getestet?--hs

Naja... was heißt schon "gründlich" in dem Zusammenhang...(?) Ja, ich habe es getestet. Und auch ein paar kleine Benchmarks laufen lassen. Wenn es nur um das Sortieren eines einfachen int-arrays geht, scheint die Implementierung oben sogar (um den Faktor 1.5 - 2) *schneller* zu sein, als qsort bzw. qsort_ (siehe unten). Falls das von unabhängiger Seite verifiziert werden kann, wäre das m.E. ein sehr gutes Beispiel zum Thema SoftwareOptimierung... ;-) [Regel 1: "Optimiere nicht"]

Ich habe jetzt dein quicksort() mal getestet mit 250000 Zeilen, auch gleiche darunter: Sie sortiert korrekt. --hs

Ich hatte auch mal solche elementaren Varianten entwickelt, auch mit Format-String. Letztlich bin bei meinem qsort_ gelandet ;-), weil die absolut alles kann. --hs

Jep, man verwendet eben jeweils das angemessenste Tool um eine best. Aufgabe zu lösen: manchmal genügt eben eine elementare Implementierung und manchmal eben nicht... ;-) // Das YAGNI-Prinzip (YouArentGonnaNeedIt) zusammen mit dem Streben nach einfachem Design (das bei mir stark ausgeprägt ist) hat mich eben zu der oben angegebenen Lösung geführt.

..Anmerkung: Nicht stabil..

Ist möglicherweise meine Variante stabil... (?) -- hs

Nein, wieso sollte sie? Beim Swappen kann es auch bei deiner Variante vorkommen, dass über ein gleiches Element hinweg geswappt wird. Wie sollte denn da die Stabilität kommen? --??

Kann mir hier jemand erklären, was unter "stabil", "nicht stabil" in Bezug auf die oben geposteten Implementationen von QuickSort überhaupt zu verstehen ist?

Stabil ist ein SortierAlgorithmus? dann, wenn er die Reihenfolgebeziehung zwischen gleichen Elementen nicht ändert.

Bei vielen Quicksort-Implementierungen fällt mir auf (und das betraf auch die obigen), dass keine Rücksicht auf den Worst-Case in Bezug auf den Stackverbrauch genommen wird, der in ungünstigen Fällen ~N sein kann. Damit hatte ich auf Systemen mit begrenztem Stack schon einige Probleme. Dabei wäre es leicht, den Stackverbrauch ~ln(N) zu gestalten:

if (LINKER_BEREICH<RECHTER_BEREICH) { qsort(LINKER_BEREICH); qsort(RECHTER_BEREICH); } else { qsort(RECHTER_BEREICH); qsort(LINKER_BEREICH); }

Weshalb sollte den das den Stackverbrauch senken? Dies führt lediglich dazu, dass im Baum bei der QuickSort/Analyse die linke und rechte Hälfte des Baumes vertauscht werden. Das bringt aber gar keine Änderung im Stackverbrauch. Anders gesagt: alles was man damit erreicht, ist, dass der Stackverbrauch eher gegen Schluss zunimmt, da die aufwendigen Aufrufe gegen Schluss gemacht werden.

Entschuldige, du hast natürlich vollkommen Recht. So wie ich es oben beschrieben habe, stimmt das nicht. Der entsprechende Teile des Originalcode sieht so aus:

if (j-l < r-i) { if (l < j) { sort_quick(l,j); } if (i < r) { l = i; if (l < r) { goto restart; /* sort_quick(i,r); */ } } } else { if (i < r) { sort_quick(i,r); } if (l < j) { r = j; if (l < r) { goto restart; /* sort_quick(l,j); */ } } }

und vermeidet im längeren Zweig den rekursiven Aufruf der Funktion. Auf diese Weise entsteht das oben beschriebene Verhalten. Ich wollte mir die ganzen Spezifika ersparen und habe unzulässig verkürzt. --hl

Tatsaechlich, das sollte funktionieren. Dann kann man aber auch argumentieren, dass ein guter Compiler die 'goto restart;' Anweisung ueberfluessig macht, weil er TailRecursion von selbst aufloesen kann. Dies, wiederum fuehrt zu deiner ersten Methode, welche deshalb unter der Bedingung eines guten Compilers trotzdem den Stackverbrauch auf O(log(n)) senken sollte. -- ThomasHolenstein

..Rücksicht auf den Worst-Case in Bezug auf den Stackverbrauch nehmen..

Obwohl ich bisher keine Probleme hatte, weil ein Aufruf geschätzt nur 20-50 Bytes Stack braucht und ich 384MB RAM + 500 MB Swap habe, ist das pauschal eine gute Idee, die ich das Interesse habe, mal umzusetzen.

Ich habs getestet: Kein Unterschied!:

 Rekursive Calls:
 29: 220 K,   6863 lines, Quellkode
 41: 1.5 MB,  find-Listing
 45: 2.7 MB,  find-Listing
 50: 70.3 MB! len50random_numbers, 1 Mlines; 20 sec!
 21: dito,    vorsortiert; ln(N)+1

Bei zufallsverteilten Daten ist ~ln(N) zu erwarten. Wenn die Daten aber im Worst-Case ungünstig verteilt sind, kann der Stackbedarf stark ansteigen (habe ich erlebt). Dann kann es zu "unerklärlichen" Abstürzen kommen. --hl

Für den Zeitbedarf gilt übrigens ~n*ln(n). --hs

Wie gesagt, das ist normal bei einigermaßen gutmütig verteilten Testdaten.

Im Worst-Case Fall hat man N Calls.

@hs: Dann habe ich noch eine Frage. Warum übergibst du bei Deinem qsort_ eine eigene swap-Funktion, statt der im Standard-qsort üblichen Strukturlänge?

Nicht nur das, ich verwende auch uint-Indexe.

Diese Ausgestaltung ist ultimativ universell!

Ich hatte schon mal in der Swap 40 Zeilen komplexen Kode! --hs

..uint-Indexe..

Das heißt aber dann, dass du in cmp und swap explizit die zu sortierende Datenstruktur adressierst!? D. h. cmp und swap sind nicht wiederverwendbar und dein qsort_ nicht reentrant? -- hl

#if defined(DOS) static void sortl_swap(register unsigned l, register unsigned r) { register struct sl_s HUG *t; t= (*hS(mps,l)).p; (*hS(mps,l)).p= (*hS(mps,r)).p; (*hS(mps,r)).p= t; return; } #else

Das ist ein kleines Beispiel.

Dann gibt es den Fall, daß man 6 Objekte verschiedener Art

mitsortieren muß - quasi mitschleppen.

Warum sollte das nicht reentrant sein?--hs

..Swap 40 Zeilen komplexen Kode..

Komplexes swap heißt aber: langsames Sortieren. Da wäre es vermutlich schneller, eine zusätzliche Pointer-Tabelle aufzubauen, zunächst diese Pointer zu sortieren und dann in einem Durchlauf die Daten zu ordnen. -- hl

Manche Aufgaben/Objekte waren so komplex, daß ich eine externe Swap() brauchte.

Andernfalls hätte ich eigens Objekte extra zum Sortieren anlegen müssen, etc... --hs