Re: strange problem of sorting
On 2007-07-06 16:22, abracadabra wrote:
I am reading an old book - Programming Pearls 2nd edition recently. It
says, "Even though the general C++ program uses 50 times the memory
and CPU time of the specialized C program, it requires just half the
code and is much easier to extend to other problems." in a sorting
problem of the very first chapter.
I modified the codes in the answer part, ran it and found it is almost
the contrary case. The qsortints.c is the C code that uses the qsort
function defined in stdlib.h. The sortints.cpp uses STL sort. The
bitsort.c uses the method of bitmap in the book. To my surprise, the
bitmap method is slowest! The qsort method slower, the sort fastest.
It is totally different from what is said in the book!
I repeated the experiment using Visual Studio 2005 on a Windows XP
machine, and mingw32(gcc 4.2.0), the result is the same:
sort>qsort>bitmap.
Here goes the code.
[snip]
Any suggestions?
The book is outdated?
It's really no surprise that std::sort is faster than qsort, it's much
easier to optimise and (to my understanding) often uses introspective
sort, which has slightly better worst case performance than quicksort
(though there's probably nothing stopping someone to use the same
algorithm in qsort).
--
Erik Wikstr?m