#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 s(T* t, int i, int j) {
if (t[i]>t[j]) {
T tmp=t[i];
t[i]=t[j];
t[j]=tmp;
}
}
template <typename T>
void batchersort(T* t, int MAX) {
if (MAX==7) {
s(t, 0, 4);
s(t, 1, 5);
s(t, 2, 6);
s(t, 0, 2);
s(t, 1, 3);
s(t, 4, 6);
s(t, 2, 4);
s(t, 3, 5);
s(t, 0, 1);
s(t, 2, 3);
s(t, 4, 5);
s(t, 1, 4);
s(t, 3, 6);
s(t, 1, 2);
s(t, 3, 4);
s(t, 5, 6);
}
}
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;
int size=7;
double* a=new double[size];
for (int i=0; i<size; ++i) a[i]=i;
int repetition=1<<19;
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<<"std::sort: "<<sorttime<<endl;
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
wikipediasort(a, size);
}
double wikipediatime=sw.elapsed()-basetime;
cout<<"wikipedia: "<<wikipediatime<<endl;
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
yaneuraosort(a, size);
}
double yaneuraotime=sw.elapsed()-basetime;
cout<<"yaneurao: "<<yaneuraotime<<endl;
sw.reset();
for (int t=0; t<repetition; ++t) {
random_shuffle(a, a+size);
batchersort(a, size);
}
double batchertime=sw.elapsed()-basetime;
cout<<"batcher: "<<batchertime<<endl;
}