Während für eine theoretische betrachtung die gesamtlaufzeit in landau notation ja ganz nett ist, spielt in der praxis der unsichtbare konstate faktor meist eine recht grosse rolle. In vielen Anwendungen besteht in der laufzeit ein recht grosser unterschied zwischen vergleich und vertauschung. Nehmen wir einmal in C eine reihe von strings: das vertauschen der pointer ist sehr schnell (2 mal xor) aber der vergleich kann bei längeren strings schonmal ne weile dauern. Hier möchte man vermutlich gerne eine recht geringe menge an vergleichen und würde dafür einige vertauschungen mehr in kauf nehmen. Ich denke es sollte hier eine genauere betrachtung geschehen, in wie weit man quicksort (oder auch introsort) in die eine oder andere richtung beeinflussen kann, nicht zuletzt indem man es als 3-way sort auslegt. Betrachtungen in landau symbolen von der anzahl der vergleiche und vertauschungen wären hier für die praxis wohl wesentlich besser. Einmal als beispiel: vergleiche ich per GNU std::sort (ein introsort) 24000 zufällige zahlen, so komme ich (im aktuellen testfall) auf fast 420000 vergleiche, mit der microsoft qsort (auch ein introsort) variante sind es lediglich knapp 66000. Ist jetzt der vergleich wesentlich teurer als ein vetauschen bedeutet das in der gesamtlaufzeit ein geschwindigkeitsvorteil von 6 fach! (nicht signierter Beitrag von 192.0.2.255 12:35, 14. Sep. 2009 (CEST) )