[ create a new paste ] login | about

Link: http://codepad.org/ofzleDmL    [ raw code | output | fork ]

C++, pasted on Dec 1:
#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;
}


Output:
1
2
3
4
std::sort: 0.468346
wikipedia: 0.18687
yaneurao: 0.168168
batcher: 0.250902


Create a new paste based on this one


Comments: