Problem mit Quicksort-Implementierung

[Apollonius]

Dein Dreieckstausch sieht... interessant aus.

[alzaimar]

ACHTUNG! Hier kommt ein versteckter Hinweis!

Zitat von Apollonius:

Dein Dreieckstausch sieht... interessant aus.

Das war der versteckte Hinweis.

[Satty67]

Ach Du lieber Gott

Wenn zwei den Wald vor lauter Bäumen nicht sehen, sind dann beide dadurch entschuldigt, dass Sie zu zweit waren?

Bei Daniels Code fehlte damals der Insertion-Aufruf, weshalb der bei mir auch nicht funktionierte

[quendolineDD]

Ist mir beim ersten drüber blicken auch gar nicht aufgefallen
Aber bei Wikipedia sieht der Pseudocode wesentlich schlanker aus, als diese Implementierung von QuickSort.

[Satty67]

Ich hatte ihm ja meinen Code angeboten, da ist der QuickSort Teil kleiner und Insertion gleich. Zudem ist er auch noch 10% schneller, aber er will seinen Code zum Laufen bringen, was ich verstehen kann.

Das er im Zweifel aber nur Insertion genommen hätte, statt meinen, hat mich doch erschreckt

[alzaimar]

Satty67,

wäre es Dir möglich, eine kleine Applikation zu schreiben, die die Performanceunterschiede zwischen dem generischen Quicksort und der Variante mit InsertionSort belegt? Ich meine mich zu erinnern, das eine schlanke QS-Implementierung mittlerweile (und Aufgrund optimierender Compiler und CPU Code-Cache) nicht mehr langsameer ist. Da man darüber nicht diskutieren muss, sondern Fakten sprechen lassen kann, wäre es wirklich toll, wenn Du das belegen könntest. Eine iterative Variante des QS sollte zudem auch schneller sein, aber das ließe sich -ein geeignetes kleines Testframework vorausgesetzt- sicherlich belegen/widerlegen.

[Satty67]

Hallo alzaimar,

sowas hab' ich sogar schon geschrieben... Also eine Plattform, mit der ich InsertSort und Quicksort teste bzw. Varianten davon und Kombinationen incl. Kontrollausgabe ob auch richtig sortiert wird. Ist noch ein Überbleibsel aus dem letzten Marathon, bei dem ich mich der SkipList geschlagen geben musste

Ich werd' das heute nach der Arbeit etwas überarbeiten, im jetzigen Zustand möchte ich den Code niemandem zumuten. Ich lagere am besten jede Sortier-Routine in eine Extra Unit aus und poste dann heute Abend die Testplattform.

[user0815]

Habe hierzu diesen netten Link gefunden: http://www.stefan-baur.de/cs.algo.insertionsort.html
hmm, besser diesen wegen der Übersicht: http://www.stefan-baur.de/cs.algo.sort.html

[Satty67]

Ok, hab' mein Chaos-Projekt zum Testen von Sortierverfahren "etwas" aufgeräumt und die Sorter in Units ausgelagert. Sollte so nicht schwer sein, einen eigenen Sorter zum Vergleichen zu implementieren.

Ich will kein Gemecker, wegen der Programmierung, das war vorher noch wesentlich chaotischer, jetzt geht das etwas.

Drin sind BubbleSort, SelectionSort, QuickSort (Rekursiv) aus dem Thread-Beispiel von Delphi und InsertSort. Wobei ich bei QuickSort einen unnötigen Swap noch umgangen hab. Zusätzlich noch QuickInsertSort, das aber bei Speicher-Sortieren seine Vorteile nicht ausspielen kann und QuickSort (Iterativ), wobei ich etwas Probleme beim umsetzten des Codes hatte. Für Strings musste ich eine zusätzliche Prüfung einbauen.

Wer will, kann seinen Code einbauen und Testen oder das ganze auf Dateien anwenden, um z.B. die Vorteile von QuickInsertSort zu testen.

PS: Die Exe ist mit dabei und wer FastMM4 nicht verwendet, einfach aus der Deklaration rauswerfen.

PPS: Schwer es genau zu sagen, aber man sieht eine Tendenz. QuickInsertSort ist beim Sortieren von Speicherlisten sogar minimal langsamer. Überhaupt spricht bei der Performance von Quicksort nichts dagegen, für Speicherlisten nur QuickSort zu nehmen. Für Dateien ist die SkipListe besser, die beim Speichersortieren wohl wegen kompletten Kopieren der Liste ein Putt liefert.

Ergebnisse:

Code:

_358 ms für 10.000 Int64-Elemente mit Bubble-Sort
_214 ms für 10.000 Int64-Elemente mit Selection-Sort
__49 ms für 10.000 Int64-Elemente mit Insertion-Sort
___0 ms für 10.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt)
___1 ms für 10.000 Int64-Elemente mit Quick-Sort (iterativ)
___1 ms für 10.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

3770 ms für 10.000 String-Elemente mit Bubble-Sort
1389 ms für 10.000 String-Elemente mit Selection-Sort
1068 ms für 10.000 String-Elemente mit Insertion-Sort
___5 ms für 10.000 String-Elemente mit Quick-Sort (rekursiv, kompakt)
___6 ms für 10.000 String-Elemente mit Quick-Sort (iterativ)
___6 ms für 10.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

_357 ms für 2.500.000 Int64-Elemente mit Quick-Sort (rekursiv, kompakt)
_370 ms für 2.500.000 Int64-Elemente mit Quick-Sort (iterativ)
_417 ms für 2.500.000 Int64-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)

3150 ms für 2.500.000 String-Elemente mit Quick-Sort (rekursiv, kompakt)
3596 ms für 2.500.000 String-Elemente mit Quick-Sort (iterativ)
3652 ms für 2.500.000 String-Elemente mit Quick/Insert-Sort (rekursiv, kompakt)