Problem mit Quicksort-Implementierung

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