Hi Pascal.

22-May-04 14:23:36, Pascal Schmidt wrote to Jasen Betts


 PS> Hi Jasen! :-)

 PS>>> Quicksort has a worst-case of O(n^2), in the case of an already
 PS>>> sorted array. But your right, on random data it's O(n log n)
 JB>> Most implementations of qsort() have code to handle that case
 JB>> better.

 PS> Hard to check for, I'd think.

typically what they do is sample the list at three points and that the
middle of the three as the pivot

this strategy works well on sorted data and also slightly improves
performance on random data.

it's still possible to order data such that it'll be hard to qsort
but the ordering required to do this is much more compleex than simple
sorted order, and much less likely to be encountered in real life.

 -=> Bye <=-

---