Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 12:08:17
I have done only very few tests. For the moment the theory doesn't seem to
pay off. Although the complexity should be close to O(N) for sorted input,
std::sort performs incredibly well on such sorted input (MS' implementation
is an introspective sort).
To use a technical term, std::sort is currently spanking my smoothsort very
This will need more tests, and again, my implementation is not optimized.
For example I have kept iterator's arithmetic generic so that it may work on
std::list. A hint that I can do much better is that even std::make_heap,
std::sort_heap outperforms my current implementation.
Compiler : Visual Studio 2008, x64 platform, all optimizations known to me
Processor : Intel Q6600.
-- Edouard > -----Original Message----- > From: boost-bounces_at_[hidden] [mailto:boost- > bounces_at_[hidden]] On Behalf Of Christopher Jefferson > Sent: dimanche 14 décembre 2008 16:06 > To: boost_at_[hidden] > Subject: Re: [boost] [library submission] smoothsort > > I would certainly be interested in such a library. > > Have you benchmarked it against std::sort in any compilers? > > Chris > > On 14 Dec 2008, at 14:18, Edouard A. 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. > > > > > > > > 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). 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. > > > > > > > > Kind regards. > > > > > > > > -- > > > > > > > > Edouard Alligand > > > > _______________________________________________ > > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost > > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk