Diese Posts stammen ursprünglich aus einem OT-Thread, der im Moderator-Interna zu finden ist.
EDIT: Wurscht, ich mach einfach nen normalen Introsort draus. :»
Mal ne kleine Diskussion am Rande, an die Aloritmen-Guys hier, sprich: Fyx, Monkey, und wer sich eben noch so angesprochen fühlt.
Ich mag nen brauchbaren Qsort implementieren. Den Pivot wähle ich als den Mittleren dreier zufälliger Listeneinträge.
Das Verfahren skaliert für große Werte ausgezeichnet. Wenn meine Partition allerdings bereits sehr klein ist, wird es natürlich immer wahrscheinlicher, dass sich meine zufälligen Zahlen überschneiden. Die Wahrscheinlichkeit wird durch die Konkruenzen einfach zu hoch, als das ich davon ausgehen kann, dass ich da nicht zu viele Zufallszahlen generieren muss, bis eine passt.
Die Geschichte sowie die Minimalanzahl für eine Partition von drei Elementen ist insofern natürlich sowieso nicht tragisch, weil ein qsort für so kleine Listen sowieso schlecht skaliert, und ich auf ein anderes Sortierverfahren zurückgreifen muss.
Die eigentiche Frage: Weiß einer von euch was für ein Verfahren als zweites Sortierverfahren ab welcher Größe brauchbar wäre? Für Vorschläge die ich in meinen Tests und Überlegungen weiter berücksichtigen kann wäre ich dankbar.
Aufwand für Schlüsselvergleiche und Bewegungskosten sind beide für den general purpose-Fall, wobei wir meistens wahrscheinlich eher nur Referenzen verschieben.
Insofern die Rekursionstiefe gegen das Maximum geht, weiche ich natürlich auf einen anderen Algo (heapsort) aus.
