3 ms·
You can get another 2x speedup if you choose the pivot better. Right now it seems you're doing median of 3. When you're doing Order Statistics (ie Selection/Qu
by susi22 13y ago
You can get another 2x speedup if you choose the pivot better. Right now it seems you're doing median of 3.
When you're doing Order Statistics (ie Selection/Quickselect) with 1M elements you should be very very close to the theoretical optimum (1.5N) for complexity. See my comment here:
https://news.ycombinator.com/item?id=6629117 https://news.ycombinator.com/item?id=6629117
If you're interested in choosing the best strategy.
HTH
- naftaliharris 13y agoNeat! A quick skim of the referenced article in that comment (http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6193457 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6193457) shows that it solves a problem I'd wondered about for a while now, about how to optimally choose the pivots when computing order stats. (Yeah, I'm just doing median of 3 right now). If you want to sort the whole list, then clearly you want the pivots to be as near to the median as possible. But if you just want an order stat, then that's not necessarily true; if you wanted, say, the 10th percentile, my gut feeling would be that you should aim for your first pivot to be roughly the 20th percentile or so. I'll read that article more closely and see if I can improve even more. Thanks, that's really helpful!