#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#ifdef _MSC_VER
#include <ctime>
class Stopwatch
{
std::clock_t start;
public:
Stopwatch() { reset(); }
void reset() { start=std::clock(); }
double elapsed() {
std::clock_t finish=std::clock();
return double(finish-start)/CLOCKS_PER_SEC;
}
};
#endif //_MSC_VER
#ifndef _MSC_VER
#include <sys/time.h>
class Stopwatch
{
struct timeval start;
static double value(struct timeval& tv) { return tv.tv_sec+(double)tv.tv_usec*1e-6; }
public:
Stopwatch() { reset(); }
void reset() { gettimeofday(&start, NULL); }
double elapsed() {
struct timeval now;
gettimeofday(&now, NULL);
return value(now)-value(start);
}
};
#endif //_MSC_VER
using namespace std;
template <typename T>
void wikipediasort(T* data, int n) {
int i, j;
T tmp;
for (i = 1; i < n; i++) {
tmp = data[i];
for (j = i; j > 0 && data[j-1] > tmp; j--) {
data[j] = data[j-1];
}
data[j] = tmp;
}
}
template <typename T>
void yaneuraosort(T* t, int MAX) {
for (int i = 1; i < MAX; i++)
{
T tmp = t[i];
if (t[i-1] > tmp)
{
int j = i;
do {
t[j] = t[j-1];
--j;
} while ( j > 0 && t[j-1] > tmp);
t[j] = tmp;
}
}
}
int main()
{
srand(static_cast<unsigned int>(time(0)));
Stopwatch sw;
cout<<"size\trepetition\tstd\twiki\tyane\ty/w\n";
for (int logsize=2; logsize<=16; ++logsize) {
int size=1<<logsize;
double* a=new double[size];
for (int i=0; i<size; ++i) a[i]=rand();
int repetition=(1<<(24-logsize))/logsize/logsize;
cout<<size<<'\t'<<repetition<<'\t';
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
}
double basetime=sw.elapsed();
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
sort(a, a+size);
}
double sorttime=sw.elapsed()-basetime;
cout<<'\t'<<setprecision(4)<<sorttime;
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
wikipediasort(a, size);
}
double wikipediatime=sw.elapsed()-basetime;
cout<<'\t'<<setprecision(4)<<wikipediatime;
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
yaneuraosort(a, size);
}
double yaneuraotime=sw.elapsed()-basetime;
cout<<'\t'<<setprecision(4)<<yaneuraotime;
cout<<'\t'<<setprecision(4)<<yaneuraotime/wikipediatime<<endl;
}
}