Re: [boost] [sorting] Taking away quicksort and mergesort

From: Herve Bronnimann (hervebronnimann_at_[hidden])
Date: 2007-03-18 17:45:04

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_at_[hidden]>
Date: Sun, 18 Mar 2007 13:03:27 
To:boost_at_[hidden]
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?
> 
> http://en.wikipedia.org/wiki/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