David Abrahams wrote:
on Sat Mar 17 2007, Rene Rivera <grafikrobot-AT-gmail.com> wrote:
Hervé Brönnimann wrote:
Rene: What do you mean by "tighter complexity bounds"? Just curious, I meant tighter guarantees of the complexity of the algorithm, in big O. The customary quicksort is usually O(NlogN) on most sequences, but it can be as high as O(N2). The quicksort variant I have has a guaranteed worst case of O(NlogN). The price for that guarantee is a larger K overall. Which if one is using objects for which the comparison is expensive is a better trade off.
How is your version different from introsort?
It's different in that it's not introsort ;-) It's the 3-way partitioning quicksort by Bentley and McIlroy <http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/spe862jb.pdf>. Analysis of the complexity in this presentation <http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf>. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo