Qsort-Optimierung, Ideensammlung

[Mog]

Bei uns an der Uni ist für Listen mit 6 oder weniger Elementen in der Regel Insertion Sort üblich. Der scheint da wohl ganz brauchbar zu funktionieren, auch wenn er für größere Eingaben natürlich grausam skaliert.

...

Insertion ist auch das, was ich aktuell verwende, nur kommt mir das doch etwas ungut vor. Ich überlege mir da noch mit einem Heap anzusetzen und zu vergleichen. Gerade dieses unschöne Quadrat soll aus der Laufzeit heraus. Mal schauen, wie das für beliebige Permutationen der entsprechenden Längen aussieht.

Bevor ich das allerdings mache, muss ich erst herausfinden, wie der Compiler Generics genau auflöst, um die Datenverschiebungen besser einschätzen zu können.

Einen Tipp noch, um den Speicherbedarf beim Quick Sort ein wenig zu verringern: sortier nur die kleinere Partition rekursiv. Für die größere kannst du in der Inplace Variante von QSort (ich nehme an, die verwendest du) Start- bzw. End-Index neu setzen und iterativ arbeiten.

...

Mache ich bereits - ich frage mich generell, warum man so wenig von diesem Trick liest, wenn man herum sucht.

Edit: wäre vielleicht ganz nett, die zwei Posts hier in einen extra Thread im Programmierforum zu schieben, das interessiert sicher auch andere.

...

Kannst du gerne machen, wenn du magst.