/*---------------------------------------------------------------------------
File name: sort-efficiency.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/29/2007 17:40:41
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
Problem statement:
---------------------------------------------------------------------------
I was asked "Which sorting algorithm is most efficient for random data?".
Analysis:
---------------------------------------------------------------------------
In this article, we consider four approaches of sorting:
1. STL sort + function pointer;
2. STL sort + functor;
3. STL sort;
4. qsort.
A few ouputs are shown in the Sample ouput section. We conclude that:
a. approach 2 is as efficient as approach 3. The former is more flexible,
since you can define what it means by "a>b" yourself.
b. approach 1 takes longest time to finish. Thus you may want to avoid using
function pointers.
c. approach 4 is less efficient than approach 2 and 3. Or we can conclude,
legacy C code is less efficient than standard C++ code.
Sample output:
---------------------------------------------------------------------------
Test #1, size of input is 13388000
Function pointer: 6.549 seconds.
Functor: 4.166 seconds.
Standard C++: 4.166 seconds.
qsort: 6.559 seconds.
Test #2, size of input is 18258761
Function pointer: 9.073 seconds.
Functor: 5.728 seconds.
Standard C++: 5.718 seconds.
qsort: 8.463 seconds.
Test #3, size of input is 12957326
Function pointer: 6.329 seconds.
Functor: 3.995 seconds.
Standard C++: 3.996 seconds.
qsort: 5.939 seconds.
Test #4, size of input is 12806571
Function pointer: 6.229 seconds.
Functor: 3.936 seconds.
Standard C++: 3.965 seconds.
qsort: 5.799 seconds.
Test #5, size of input is 10091271
Function pointer: 4.847 seconds.
Functor: 3.064 seconds.
Standard C++: 3.085 seconds.
qsort: 4.536 seconds.
Test #6, size of input is 13669040
Function pointer: 6.679 seconds.
Functor: 4.196 seconds.
Standard C++: 4.196 seconds.
qsort: 6.209 seconds.
Test #7, size of input is 18539801
Function pointer: 9.233 seconds.
Functor: 5.818 seconds.
Standard C++: 5.829 seconds.
qsort: 8.572 seconds.
Test #8, size of input is 12031356
Function pointer: 5.828 seconds.
Functor: 3.676 seconds.
Standard C++: 3.665 seconds.
qsort: 5.408 seconds.
Test #9, size of input is 16859086
Function pointer: 8.342 seconds.
Functor: 5.287 seconds.
Standard C++: 5.258 seconds.
qsort: 8.262 seconds.
Test #10, size of input is 19100681
Function pointer: 9.503 seconds.
Functor: 5.999 seconds.
Standard C++: 5.999 seconds.
qsort: 8.932 seconds.
Reference:
---------------------------------------------------------------------------
1. Scott Meyers, Effective C++, Effective STL, etc.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <ctime>
#include "hjns.h"
#include <cstdio>
#include <cstdlib>
using namespace std;
inline int cmp(const void* a, const void *b)
{
return *(int*)(a)-*(int*)(b);
}
inline bool funcPointer(int a, int b)
{
return a>b;
}
struct functor : public binary_function<int, int, bool>
{
bool operator()(int a, int b)
{
return a>b;
}
};
int main()
{
int i;
for(i=1; i<11; ++i)
{
hj::number::random rd;
// size if random between 10000000 and 20000000, inclusive.
int kSize = rd(10000000, 20000000);
int* a = new int[kSize];
// generate a random array consisting of 1..kSize
hj::number::randPerm(a, kSize);
// make all four input data sets the same
vector<int> v1(a, a+kSize);
vector<int> v2(a, a+kSize);
vector<int> v3(a, a+kSize);
cout<<"\nTest #"<<i<<", size of input is "<<kSize<<endl;
// function pointer approach
{
clock_t start(clock());
sort(v1.begin(), v1.end(), funcPointer);
clock_t elapsed = clock() - start;
cout<<"Function pointer: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// functor approach
{
clock_t start(clock());
sort(v2.begin(), v2.end(), functor());
clock_t elapsed = clock() - start;
cout<<"Functor: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// standard C++
{
clock_t start(clock());
sort(v3.begin(), v3.end(), greater<int>());
clock_t elapsed = clock() - start;
cout<<"Standard C++: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
// qsort (legacy C library function)
{
clock_t start(clock());
qsort((void*)a, kSize, sizeof(int), cmp);
clock_t elapsed = clock() - start;
cout<<"qsort: "<< double(elapsed)/CLOCKS_PER_SEC <<" seconds.\n";
}
delete [] a;
}
return 0;
}
