Boost logo

Boost :

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
> performances
> > on containers supporting random access iterators (in other words,
> > smoothsorting a std::list is quite slow).
> Why? Is the complexity bound still respected?
[Edouard A.]

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.

[Edouard A.]

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/

Without profiling:

        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, gregod at, cpdaniel at, john at