The Most Important Algorithms

Re:The Most Important Algorithms by _delirium on Tuesday July 06, 2010 @04:06AM (#1490336)

The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms. If you want an O(nlogn) worst-case, introsort combines quicksort, which is fast on average but O(n^2) worst-case, with a fall-back to an O(nlogn) heapsort, with a guarantee that it'll never take more than O(nlogn) before it falls back, making it still worst-case no worse than O(nlogn). It'll of course be a constant-factor slower in those fall-back cases than if you had just used heapsort or something directly, but it'll asymptotically be no worse, and on average will get you the nice quicksort win.

Link: http://en.wikipedia.org/wiki/Introsort

[ Parent | on HN ]

Re:The Most Important Algorithms by beagle3 on Tuesday July 06, 2010 @08:43AM (#1490783)

> The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms.

I don't think that's true if you average over the available distribution of _implementations_ in the wide. Almost all implementations do one to three of the "crimes" I mentioned above. And frankly, I've met too much real world cases that triggered an n^2 behaviour on an existing implementation to ever settle for anything with worse than n*log n worst case.

If you're looking for the fastest-in-both-theory-and-practice algorithm, that's TimSort, but it's not in place. The places _in practice_ where Quicksort is the right answer are few and far between. I haven't seen any in the last 10 years.

[ Parent | on HN ]