プログラマ専用SNS ミクプラ

コード:

#include <stdio.h>
#include <time.h>

int x[10000000];

// Exchanging i-th value and j-th value
void swap(i,j){
	int tmp;
	tmp=x[i];
	x[i]=x[j];
	x[j]=tmp;
}

// Decision of the median between left and right
int median(left,right){
	int mid, i;
	mid=(left+right)/2;
	if(x[left]>x[mid]) swap(left, mid);
	if(x[mid]>x[right]) swap(mid, right);
	if(x[left]>x[mid]) swap(left, mid);
	swap(mid,right);
}

int divide(int start, int end)
{
	int i,j,k,pivot,tmp;
	median(start,end);
	pivot=end;
	i=start;
	j=end-1;
	while(1){
		while(x[i] < x[pivot]) i=i+1;
		while(x[pivot] < x[j] && j>i) j=j-1;
		if(j<=i) break;
		tmp=x[i];
		x[i]=x[j];
		x[j]=tmp;
		i=i+1;
		j=j-1;
	}
	tmp=x[i];
	x[i]=x[pivot];
	x[pivot]=tmp;
	return i;
}
void quick_sort(int start, int end)
{
	int s;
	if(end<=start) return;
	s=divide(start, end);
	quick_sort(start, s-1);
	quick_sort(s+1, end);
}


main ()
{
	int i, j, n;
	int iseed, icount, tmpdata;
	double time, timerstart, timerend;
	printf("Quick sort program.\n");
/* random number seed */
	printf("Please input the seed: ");
	scanf("%d", &iseed);
	for(j=1; j<=10; j=j+2){
		n=j*1000000;
		icount=0;
/* random number junbi */
		srand(iseed+j);
/* Throwing away first 10 random numbers */
		for(i=1; i<10; i=i+1) {rand();}
/* Data creation */
		while(icount<n){
			tmpdata=rand();
			if(tmpdata>100000000){
				x[icount]=tmpdata;
				icount=icount+1;
			}
		}
/*
		for(i=1;i<n;i=i+1){printf("%d\n",x[i]);}
*/		
		quick_sort(0, n-1);
		timerstart=clock();
		quick_sort(0, n-1);
		timerend=clock();
		time=(timerend-timerstart)/CLOCKS_PER_SEC;
		printf("%d \t %f\n",n,time);
	}
	return 0;
}