Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 17:25:08
> > This implementation works on all sortable containers, with best
> > on containers supporting random access iterators (in other words,
> > smoothsorting a std::list is quite slow).
> Why? Is the complexity bound still respected?
You have a lot of std::advance within the algorithm, typically you will do
std::advance(iterator, 25) and the like. Sucks on std::list's iterators.
> Absolutely, IMO. I think we might need a general algorithms library to
> put it in.
I was thinking the same, by itself smoothsort would not justify the creation
of a library, but where to place it? And I'm sure we could figure out a nice
catalog of algorithms to implement.
>Did you use -D_SECURE_SCL=0
>Without that, anything that you do with most iterators is a dog.
\o/ You are my hero I totally forgot about that \o/
std::sort running time : 0.098
std::sort running time (sorted) : 0.024
Smoothsort running time : 0.367
Smoothsort running time (sorted) : 0.017
Press any key to continue . . .
For a 1,000,000 std::vector<long>. And I'm sure it's possible to improve my
implementation as the processing for high entropy input is not very good.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk