According Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort
is about 670% faster than std::qsort
due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help me to explain this strange behavior?
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
const size_t LARGE_SIZE = 100000;
struct rnd {
int operator()() {
return rand() % LARGE_SIZE;
}
};
int comp( const void* a, const void* b ) {
return ( *( int* )a - *( int* )b );
}
int main() {
int ary[LARGE_SIZE];
int ary_copy[LARGE_SIZE];
// generate random data
std::generate( ary, ary + LARGE_SIZE, rnd() );
std::copy( ary, ary + LARGE_SIZE, ary_copy );
// get time
std::time_t start = std::clock();
// perform quick sort C using function pointer
std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
// get time again
start = std::clock();
// perform quick sort C++ using function object
std::sort( ary_copy, ary_copy + LARGE_SIZE );
std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}
This is my result:
C quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .
Update
Effective STL 3rd Edition ( 2001 )
Chapter 7 Programming with STL
Item 46: Consider function objects instead of functions as algorithm parameters.
Best regards,
std::clock() is not a viable timing clock. You should use a platform-specific higher resolution timer, like the Windows High Performance Timer. More than that, the way that you call clock() is that first, text is output to the console, which is included in the time. This definitely invalidates the test. In addition, make sure that you compiled with all optimizations.
Finally, I copied and pasted your code, and got 0.016 for qsort and 0.008 for std::sort.