On 10/9/10 11:23 CDT, Peter Alexander wrote:
On 9/10/10 4:53 PM, bearophile wrote:
Andrei:
Currently std.algorithm.getPivot picks the middle of the range as the
pivot, but I made it modular such that it can be improved in a number of
ways (i.e. randomized, median-of-3, median-of-5, etc).
Isn't median of 3 a better default?
Bye,
bearophile
There is no "best". They are all trade-offs between the time taken to
select the pivot and the suitability of the pivot.
Middle - Fastest, not very good
Median-of-3 - Slower, but slightly better
Median-of-5 - Slower still, but even better
Randomized - Speed depends on the random number algorithm. Suitability
is random, so could be good, could be bad, but on average it's good
enough. Has the added quality that it's practically impossible to devise
worst-case input for it (you'd need to know the generator and seed),
whereas for the other 3, a malicious user could provide data that gives
you O(n^2) complexity.
Also: in-place sorting for the median cases.
Andrei
