//file sort.c
#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void merge(double array[], int p, int q, int r)
{
int n1, n2;
int i,j,k;
n1 = q - p + 1;
n2 = r - q;
for(i = 0, k = p; i < n1; i++, k++)
L[i] = array[k];
for(i = 0, k = q + 1; i < n2; i++, k++)
R[i] = array[k];
for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)
{
if(L[i] <= R[j])
{
array[k] = L[i];
i++;
}
else
{
array[k] = R[j];
j++;
}
}
if(i < n1)
{
for(j = i; j < n1; j++, k++)
array[k] = L[j];
}
if(j < n2)
{
for(i = j; i < n2; i++, k++)
array[k] = R[i];
}
}
void merge_sort(double array[], int p, int r)
{
if(p < r)
{
int q = (p + r) / 2;
merge_sort(array, p, q);
merge_sort(array, q + 1, r);
merge(array, p, q, r);
}
}
double mergesort(double array[],int size)
{
clock_t start,end;
start = clock();
merge_sort(array,0,size - 1);
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
double insertsort(double array[],int n)
{
clock_t start,end;
int i,j;
double temp;
start = clock();
for(j=1;j<n;j++)
{
temp = array[j];
i = j-1;
while ((i>=0) && (array[i]>temp))
{
array[i+1] = array[i];
i = i - 1;
}
array[i+1] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
double shellsort(double array[], int n)
{
clock_t start,end;
int h, i, k;
double temp;
start = clock();
for (h=n/2; h>0; h=h/2)
{
for (i=h; i<n; i++)
{
temp = *(array+i);
for (k=i-h; (k>=0 && temp<*(array+k)); k-=h)
{
*(array+k+h) = *(array+k);
}
*(array+k+h) = temp;
}
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
void swap(double *a, double *b)
{
double temp = *a;
*a = *b;
*b = temp;
}
int partition(double *array, int low, int high)
{
double temp = array[high];
int i,j;
i = low - 1;
for(j = low;j<high;j++)
{
if(array[j]<=temp)
{
i = i + 1;
swap(&array[i],&array[j]);
}
}
swap(&array[i+1],&array[high]);
return i + 1;
}
void quick_sort(double *array, int low, int high)
{
int q;
if(low<high)
{
q = partition(array,low,high);
quick_sort(array,low,q-1);
quick_sort(array,q+1,high);
}
}
double quicksort(double *array, int size)
{
clock_t start,end;
start = clock();
quick_sort(array, 0, size-1);
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
double bubblesort(double *array, int size)
{
int i, j;
double temp;
clock_t start,end;
start = clock();
for (i=size-1; i>0; i--)
for (j=0; j<i; j++)
if (array[j] > array[j+1])
{
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
void init(headnode *b)
{
int i;
for(i=0;i<10;i++)
{
b[i].num = 0;
}
}
void insertelements(headnode b[],double array[],int size)
{
int i,k;
for(i=0;i<size;i++)
{
k = (int)(array[i]*10);
if(k == 10)
{
b[k-1].b_array[b[k-1].num] = array[i];
b[k-1].num = b[k-1].num + 1;
}
else
{
b[k].b_array[b[k].num] = array[i];
b[k].num = b[k].num + 1;
}
}
}
void sortelements(headnode b[])
{
int i;
for(i = 0;i < 10;i++)
{
insertsort(b[i].b_array,b[i].num);
}
}
void collectelements(double array[],headnode b[])
{
int i,j;
int k = 0;
for(i = 0;i < 10; i++)
{
for(j =0;j < b[i].num;j++)
{
array[k] = b[i].b_array[j];
k++;
}
}
}
void zerobucket(headnode b[])
{
int i,j;
for(i = 0;i < 10;i++)
{
for(j = 0;j < b[i].num;j++)
{
b[i].b_array[j] = 0;
}
b[i].num = 0;
}
}
double bucketSort(double array[],int size)
{
clock_t start,end;
start = clock();
init(b);
insertelements(b,array,size);
sortelements(b);
collectelements(array,b);
zerobucket(b);
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
void rand_array(double *array, int length, int N_max)
{
int i;
srand((unsigned)time(0));
for(i=0;i<length;i++)
array[i] =(double)(rand()%N_max)/N_max;
}
void randarray(double *array, int length)
{
rand_array(array, length,10000 );
}
void printarray(double array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
{
printf("\n");
}
printf(" %f,",array[i]);
}
printf("\n");
}
void copyarray(double *array1,double *array2,int n)
{
int i;
for(i=0;i<n;i++)
{
array2[i]=array1[i];
}
}
double aveRunTime(int i,int n,int len)
{
double sum,avetime;
int j;
sum = 0;
switch(i)
{
case 1 :
{
if(len==MAXTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(thouarray1,MAXTHOUSAND);
sum += mergesort(thouarray1,MAXTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXTENTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(tetharray1,MAXTENTHOUSAND);
sum += mergesort(tetharray1,MAXTENTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXHUNDREDTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(hutharray1,MAXHUNDREDTHOUSAND);
sum += mergesort(hutharray1,MAXHUNDREDTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
}
case 2:
{
if(len==MAXTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(thouarray1,MAXTHOUSAND);
sum += insertsort(thouarray1,MAXTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXTENTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(tetharray1,MAXTENTHOUSAND);
sum += insertsort(tetharray1,MAXTENTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXHUNDREDTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(hutharray1,MAXHUNDREDTHOUSAND);
sum += insertsort(hutharray1,MAXHUNDREDTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
}
case 3:
{
if(len==MAXTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(thouarray1,MAXTHOUSAND);
sum += shellsort(thouarray1,MAXTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXTENTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(tetharray1,MAXTENTHOUSAND);
sum += shellsort(tetharray1,MAXTENTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXHUNDREDTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(hutharray1,MAXHUNDREDTHOUSAND);
sum += shellsort(hutharray1,MAXHUNDREDTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
}
case 4:
{
if(len==MAXTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(thouarray1,MAXTHOUSAND);
sum += quicksort(thouarray1,MAXTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXTENTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(tetharray1,MAXTENTHOUSAND);
sum += quicksort(tetharray1,MAXTENTHOUSAND);
}
avetime = sum/(double)n;
return avetime;
}
if(len==MAXHUNDREDTHOUSAND)
{
for(j=1;j<=n;j++)
{
randarray(hutharray1,MAXHUNDREDTHOUSAND);
sum += quicksort(hutharray1,MAXHUNDREDTHOUSAND);
}
评论3
最新资源