testime2.c

insertion sort and merge sort running time test

#include <math.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define INFINITY 2147483647
double insertion_sort(unsigned int n,unsigned int array[]);
double merge_sort(unsigned int n, unsigned int array[]);
void rand_order(unsigned int n,unsigned int *randArray);
void asc_order(unsigned int n,unsigned int *ascArray);
void des_order(unsigned int n,unsigned int *desArray);
void merge(unsigned int A1[],unsigned int A2[],unsigned int m1,unsigned int m2);

main()
{
	unsigned int n;//the size of input array
	double time;//running time for n
	FILE *fp_asc_inser, *fp_des_inser, *fp_rand_inser,*fp_asc_merge, *fp_des_merge, *fp_rand_merge;
	int i,k;
//insertion_sort
	/*fp_asc_inser=fopen("asc_insertion4.txt","w+");
	for(i=1;i<21;i++)
	{
		n=i*2500000;
		unsigned int *array=malloc(sizeof(unsigned int)*n);
		asc_order(n, array);
		time=insertion_sort(n, array);	
		free(array);	
		fprintf(fp_asc_inser,"%-20f %-10u %-20f\n",time,n,(double)n*log((double)n)/log(2));		
	}
	fclose(fp_asc_inser);*/

	//loop k will result the slow running time
	/*fp_asc_inser=fopen("asc_insertion2.txt","w+");
	sumtime=0;
	for(i=1;i<21;i++)
	{
		n=i*2500000;
		for(k=0;k<4;k++)
		{
			unsigned int *array=malloc(sizeof(unsigned int)*n);
			asc_order(n, array);
			time[k]=insertion_sort(n, array);	
			sumtime+=time[k];
			free(array);
		}
		avertime=sumtime/4;
		fprintf(fp_asc_inser,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));		
	}
	fclose(fp_asc_inser);*/

	//fp_asc_merge=fopen("asc_merge1.txt","w+");
	//for(i=1;i<2;i++)
	//{	
		n=80000000;
		unsigned int *array=malloc(sizeof(unsigned int)*n);
		asc_order(n, array);
		/*int k;
		for(k=0;k<n;k++)
		{
			printf("%d\n",array[k]);
		}*/
		time=insertion_sort(n, array);
		/*printf("the result is \n");
		for(k=0;k<n;k++)
		{
			printf("%d\n",array[k]);
		}*/	
		free(array);
		printf("%-20f %-10u %-20f\n",time,n,(double)n*log((double)n)/log(2));		
	//}
	//fclose(fp_asc_merge);
	
	/*fp_rand_inser=fopen("rand_insertion.txt","w+");
	sumtime=0;
	printf("rand_inser begins\n");
	for(i=1;i<101;i++)
	{
		n=i*5000;		
		for(k=0;k<2;k++)
		{
			unsigned int *array=malloc(sizeof(unsigned int)*n);
			rand_order(n, array);
			time1[k]=insertion_sort(n, array);	
			sumtime+=time1[k];
			free(array);
		}
		avertime=sumtime/2;
		fprintf(fp_rand_inser,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));		
	}
	fclose(fp_rand_inser);

//merge_sort
	fp_asc_merge=fopen("asc_merge.txt","w+");
	sumtime=0;
	printf("asc_merge begins\n");
	for(i=1;i<101;i++)
	{
		n=i*500000;		
		for(k=0;k<4;k++)
		{
			unsigned int *array=malloc(sizeof(unsigned int)*n);
			asc_order(n, array);
			time[k]=merge_sort(n, array);	
			sumtime+=time[k];
			free(array);
		}
		avertime=sumtime/4;
		fprintf(fp_asc_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));		
	}
	fclose(fp_asc_merge);

	fp_des_merge=fopen("des_merge.txt","w+");
	printf("des_merge begins\n");
	sumtime=0;
	for(i=1;i<101;i++)
	{
		n=i*500000;
		for(k=0;k<4;k++)
		{
			unsigned int *array=malloc(sizeof(unsigned int)*n);
			des_order(n, array);
			time[k]=merge_sort(n, array);	
			sumtime+=time[k];
			free(array);
		}
		avertime=sumtime/4;
		fprintf(fp_des_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));		
	}
	fclose(fp_des_merge);
	
	fp_rand_merge=fopen("rand_merge.txt","w+");
	printf("rand_merge begins\n");
	sumtime=0;
	for(i=1;i<101;i++)
	{
		n=i*500000;
		
		for(k=0;k<4;k++)
		{
			unsigned int *array=malloc(sizeof(unsigned int)*n);
			rand_order(n, array);
			time[k]=merge_sort(n, array);	
			sumtime+=time[k];
			free(array);
		}
		avertime=sumtime/4;
		fprintf(fp_rand_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));
	}
	fclose(fp_rand_merge);*/
}

void rand_order(unsigned int n,unsigned int *randArray)
{
	srandom(time(0));
	unsigned int i;
	for(i=0;i<n;i++)
		*(randArray+i)=n*(float)random()/(float)0x7fffffff;
}

void asc_order(unsigned int n,unsigned int *ascArray)
{
	unsigned int i;
	for(i=0;i<n;i++)
		*(ascArray+i)=i;
}

void des_order(unsigned int n,unsigned int *desArray)
{
	unsigned int i;
	for(i=0;i<n;i++)
		*(desArray+i)=n-i;
}

double insertion_sort(unsigned int n,unsigned int array[])
{
	clock_t start,end;
	double cpu_time_used;
	start=clock();

	int i,j,key;
	for(j=1;j<n;j++)
        {
        	key=array[j];
        	i=j-1;
        	while ((i>=0) && (array[i]>key))
                {
                        array[i+1]=array[i];
                        i--;
                }
        	array[i+1]=key;
        }

	end=clock();
	cpu_time_used=((double)(end-start)/CLOCKS_PER_SEC);

	return cpu_time_used;
}

double merge_sort(unsigned int n, unsigned int array[])
{
	clock_t start,end;
	double cpu_time_used;
	start=clock();

	if(n>0)
	{
		int q=abs((0+n)/2);
		merge_sort(q, array);
		merge_sort(n-q-1, array+q+1);
		merge(array,array+q+1,q,n-q-1);
	}

	end=clock();
	cpu_time_used=((double)(end-start)/CLOCKS_PER_SEC);

	return cpu_time_used;
}

void merge(unsigned int A1[],unsigned int A2[],unsigned int m1,unsigned int m2)
{	
	unsigned int i,j;
	unsigned int B[m1+2];
	unsigned int C[m2+2];
	for(i=0;i<=m1;i++)
		B[i]=A1[i];
	for(j=0;j<=m2;j++)
		C[j]=A2[j];
	B[m1+1]=INFINITY;
	C[m2+1]=INFINITY;
	i=0;
	j=0;
	unsigned int m=m1+m2+2;
	unsigned int k;
	for(k=0;k<m;k++)
	{
		if(B[i]<=C[j])
		{			
			A1[k]=B[i];
			i++;
		}
		else
		{
			A1[k]=C[j];
			j++;
		}
	}
}