Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[Der_Unwissende]

Zitat von Phoenix:

Im Worst-Case ja. Aber auch nur da, und versuch Du mal Daten zu konstruieren die beim Quicksort zum Worst Case führen.
Vor allem, wenn man einen geschickten randomisierten Quicksort verwendet erhält man nachweislich nie den Worst-Case.

Will heissen wir ziehen hier zum Vergleich sowieso immer nur den Average-Case heran und der ist beim Quicksort mit O(n*log(n)) nunmal nachweislich am Optimum. Deswegen heisst das Ding ja auch quicksort: Weil es der schnellste zur Zeit bekannte Sortieralgorithmus ist.

Ich glaube jetzt hast du etwas zu stark pauschalisiert. Natürlich gibt es auch einen Worst-Case der erreicht werden kann, auch mit Randomisierung (gerade wenn es echt zufällig ist), aber die Wahrscheinlichkeit geht sehr sehr stark gegen 0.
Optimal ist diese Sortierung natürlich auch nicht, schließlich kann man unter gewissen Umständen sogar in linearer Zeit Sortieren.
Aber bleiben wir ruhig bei Merge- und Quicksort, die Laufzeiten sind hier einfach nur Asymptotisch angegeben, da ist doch ein wenig Relevantes versteckt (konst. Faktoren und mindest Länge). Ist deine Liste nur kurz genug, würde sich ein Bubblesort im Average-Case sogar besser machen als ein Quicksort.
Ist die Liste nur Lang genug, wirst du auch nicht glücklich mit Quicksort, gerade bei sehr großen Datenmengen spielt Mergesort dann ein paar Vorteile aus (wenn er darauf optimiert wurde).
Solange du aber Soriterungen im Speicher durchführst ist ohne frage Quicksort nicht langsam (in Kombination mit Bubblesort am schnellsten), aber ich denke mal es kommt doch eh nicht auf die paar ms mehr oder weniger an (gehe hier einfach mal von einer kleinen Liste < 10000 Elemente aus).

Aber klar, hast recht, die konstanten Faktoren beim QS sind kleiner als die des MS.

Gruß Der Unwissende