Rene: you misunderstood the meaning of the word optimal in that algorithm. There is no version of quicksort which takes n log n time in the worst case, short of doing some selection on the pivot. The algorithm you quote, iirc, is optimal on average even when the distribution has many equal elements (which in itself is an achievement since almost any version of quicksort is not going to have an average time of n log n when many elements are equal). It can still (for some particular sequence) take quadratic time. Doug McIlroy gave such a sequence in the 80s (he calls it the killer sequence since it makes almost any variation of quicksort run in quadratic time). Please, take a look at John Valois revisited version of introsort. John no longer works in academia, but at some point he posted his code online and I believe it must still be out there. It's a good read ! Herve -- Hervé Sent from my BlackBerry® wireless handheld Please excuse misspellings and typos -----Original Message----- From: Rene Rivera <grafikrobot@gmail.com> Date: Sun, 18 Mar 2007 13:03:27 To:boost@lists.boost.org Subject: Re: [boost] [sorting] Taking away quicksort and mergesort 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost