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

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2007-03-18 15:03:27

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