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 hard. 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 turned on. Processor : Intel Q6600. -- Edouard
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost- bounces@lists.boost.org] On Behalf Of Christopher Jefferson Sent: dimanche 14 décembre 2008 16:06 To: boost@lists.boost.org 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