on Sun Dec 14 2008, "Edouard A." <edouard-AT-fausse.info> wrote:
Hello,
I just finished a C++ implementation of the smoothsort algorithm (a derivative of the heapsort algorithm by Dijkstra that, in his words, "is of order N log N in the worst case, but of order N in the best case, with a smooth transition between the two").
When sorting nearly sorted containers smoothsort achieves excellent performances. If you keep sorting the same container, smoothsort may be the right algorithm for you.
Awesome. Sounds really useful.
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?
It only requires the "<" operator between two elements and the user can supply the function with a binary predicate.
To my knowledge, there is no equivalent public C++ implementation.
I was wondering if this was interesting enough to be included in the boost library.
Absolutely, IMO. I think we might need a general algorithms library to put it in. -- Dave Abrahams BoostPro Computing http://www.boostpro.com