BubbleSort.cpp

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <sys/time.h>
#include <random>

static double dtime(void);
static void bubble_sort(int *a, long n);
static int verify_sort(int *a, long n);
static double measure_sort(int *a, long n);
extern int main(void);

/*実行時間計測の関数*/
static double dtime(){
	double q;
	struct timeval tnow;

	gettimeofday(&tnow,NULL);
	q = (double)tnow.tv_sec + (double)tnow.tv_usec * 1.0e-6;

	return q;
}

/*バブルソート*/
static void bubble_sort(int *a, long n) {
	for(long i=0; i<n; i++) {
		int x,y,z=a[0];
		for(long j=0; j<n-1-i; j++) {
			int c;
			x=z;
			y=a[j+1];
			c=(x>y);
			a[j]=c?y:x;
			z=c?x:y;
		}
		a[n-1-i]=z;
	}
}

static int verify_sort(int *a, long n) {
	long i;
	for(i=0; i<n-1; i++) {
		 //printf("%lld\n",a[i]);
		if(a[i]>a[i+1]) {
			return -1;
		}
	}
	return 0;
}
/*実行時間計測*/
static double measure_sort(int *a, long n) {
	double start_time,end_time,elapsed_time;
	std::random_device rnd;
	std::mt19937 mtrnd(rnd());
	for(long int i=0;i<n;i++){
		a[i] = mtrnd();
	}
	//デバッグ用
	/*for(long int i=0;i<n;i++){
		printf("%lld\n",a[i]);
	}
	for(int i=0;i<10;i++){
		putchar('\n');
	}*/
	start_time=dtime();
	bubble_sort(a,n);
	end_time=dtime();
	elapsed_time=end_time-start_time;
	return !verify_sort(a,n)?elapsed_time:NAN;
}

extern int main() {
	static const long n[] = {
		500l, 2000l, 4000l, 6000l, 8000l, 10000l, 12000l, 14000l, 16000l, 18000l, 20000l, 22000l, 24000l, 26000l, 28000l, 30000l
	};
	long i=0;
	int *m;
	if(!(m = static_cast<int*>(malloc(sizeof(int)*n[sizeof(n)/sizeof(n[0])-1])))) {
		fputs("memory allocation failed\n",stderr);
		return EXIT_FAILURE;
	}
	for(i=0; i<sizeof(n)/sizeof(n[0]); i++) {
		long j=5;
		printf("%ld,",n[i]); fflush(stdout);
		do {
			double t=measure_sort(m,n[i]);
			printf("\t%f,",t); fflush(stdout);
            /*実行時間を表示*/
		} while(--j);
		putchar('\n');
	}

	free(m);

	exit(EXIT_SUCCESS);
}