linuxsort.c

在linux中GCC环境下对各种排序算法的比较

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

INSERT_SORT(char **A,int N)
{ int j=0;char *key;int i=0;
  for(j=0;j<N;j++)
	{ key=A[j];
	  i=j-1;
	  while(i+1>0&&strcmp(A[i],key)>0)
	    {  A[i+1]=A[i];
	       i=i-1;
            } 
         A[i+1]=key;
	}

}

//////////////////////////////////////////////////maopao_sort

maopao(char**A,int N)
{int i=0;int j=0;char *data_temp;
for(i=0;i<N;i++)
 {for(j=0;j<i;j++)
   if(strcmp(A[j],A[i])>0)
     {data_temp=A[j];A[j]=A[i];A[i]=data_temp;}
 }
}

///////////////////////////////////////////////////quick_sort
int PARTITION(char**A,int p,int r)// change the order on the spot{  char*temp;int i=p-1;int j=0;char *temp2;char*temp1;
 temp=A[r];
   for(j=p;j<=r-1;j++)//compare to the last one
   	{if(strcmp(A[j],temp)==-1)
	{i=i+1;temp2=A[j]; A[j]=A[i];A[i]=temp2;}
	}
       	 temp1=A[r];A[r]=A[i+1];A[i+1]=temp1;
     return i+1;//return the first one which is bigger than the last one	 }
void QUICK_SORT(char**A,int p,int r)//quick_sort
{int q=0; if(p<r)
    {  q=PARTITION(A,p,r);
        QUICK_SORT(A,p,q-1);
        QUICK_SORT(A,q+1,r);
    }
}

///////////////////////////////////////////////////merge_sort

MERGE(char**A,int p,int q,int r)
{int n1=q-p+1;int n2=r-q;
char **L,**R; char *big; char large;
int i=0;int j=0;int k=0;
L=malloc(sizeof(char*)*(n1+2));
R=malloc(sizeof(char*)*(n2+2));
for(i=1;i<=n1;i++)
    L[i]=A[p+i-1];
for(j=1;j<=n2;j++)
    R[j]=A[q+j];
large=(char)95;big=&large;
L[n1+1]=big;
R[n2+1]=big;
i=1;j=1;
for(k=p;k<=r;k++)
  {if(strcmp(L[i],R[j])<0)
      {A[k]=L[i];i++;}
      else 
      {A[k]=R[j]; j++;}
   }
}

void MERGE_SORT(char **A,int p,int r)
{int q=0;
   if(p<r)
      {q=(p+r)/2;
       MERGE_SORT(A,p,q);
       MERGE_SORT(A,q+1,r);
       MERGE(A,p,q,r);
      }
}




////////////////////////////////////////////////heap_sort
int PARENT(int i)
{return i/2;}

int LEFT(int i)
{return 2*i;}

int RIGHT(i)
{return 2*i+1;}



void max_HEAPIFY(char **A,int i,int heapsizeA)
{ 
  int l=LEFT(i);int r=RIGHT(i);
  int largest=0;char *temp;
   if(l<heapsizeA&&(strcmp(A[l],A[i])>0)) largest=l;
   else  largest=i;
   if(r<heapsizeA&&strcmp(A[r],A[largest])>0)largest=r;
   if(largest!=i)
   {temp=A[i];A[i]=A[largest];A[largest]=temp;//exchange
    max_HEAPIFY(A,largest,heapsizeA);
   }
}

void BUILD_max_HEAP(char **A,int N)
{ 
  int i=0;int heapsizeA=0;
    heapsizeA=N;
  for(i=(int)(N/2);i>1;i--)
    max_HEAPIFY(A,i,heapsizeA);
}


void HEAPSORT(char **A,int N)
{ 
  BUILD_max_HEAP(A,N);
  int i=0;
  char *temp; int heapsizeA=N;
for(i=N;i>1;i--)
 {temp=A[1];A[1]=A[i];A[i]=temp;
  heapsizeA--;
  max_HEAPIFY(A,1,heapsizeA);
 }
}


/////////////////////////////////////main()
main()
{  static int N;char**data;
   int *len;int i=0;int j=0;
   char *data_temp0,*data_temp1,*data_temp2,*data_temp3,*data_temp4,*data_temp5;
   char **A1,**A2,**A3,**A4,**A5;
   float timeuse1,timeuse2,timeuse3,timeuse4,timeuse5;//record the time
   struct timeval tpstart1,tpstart2,tpstart3,tpstart4,tpstart5;//record the starting time
   struct timeval tpend1,tpend2,tpend3,tpend4,tpend5;//record the ending time
   printf("INPUT THE NUMBER \nN=");
   scanf("%d",&N);int u=1;int q=0;
   for(q=0;q<N;q++)
	 u=2*u;
   N=u;
   data=malloc(sizeof(char*)*N); 
   A1=malloc(sizeof(char*)*N); 
   A2=malloc(sizeof(char*)*N); 
   A3=malloc(sizeof(char*)*N); 
   A4=malloc(sizeof(char*)*N); 
   A5=malloc(sizeof(char*)*N); 
   len=(int *)malloc(sizeof(int)*N);

srand(time(0));
for(i=0;i<N;i++)
  { len[i]=1+random( )%16;}

srand(time(0));
for(j=0;j<N;j++)
{
  data_temp0=(char *)malloc(sizeof(char)*(len[i]+1));//recording the original character
  data_temp1=(char *)malloc(sizeof(char)*(len[i]+1));
  data_temp2=(char *)malloc(sizeof(char)*(len[i]+1));
  data_temp3=(char *)malloc(sizeof(char)*(len[i]+1));
  data_temp4=(char *)malloc(sizeof(char)*(len[i]+1));
  data_temp5=(char *)malloc(sizeof(char)*(len[i]+1));
    for(i=0;i<len[i];i++)//record the length of each character
    { 
     data_temp0[i]=(char)(65+random()%26);
     data_temp1[i]= data_temp0[i];
     data_temp2[i]= data_temp0[i];
     data_temp3[i]= data_temp0[i];
     data_temp4[i]= data_temp0[i];
     data_temp5[i]= data_temp0[i];
    
    }
   data_temp0[i+1]='\0';
   data_temp1[i+1]='\0';
   data_temp2[i+1]='\0';
   data_temp3[i+1]='\0';
   data_temp4[i+1]='\0';
   data_temp5[i+1]='\0';
   
   data[j]=data_temp0;
   A1[j]=data_temp1;
   A2[j]=data_temp2;
   A3[j]=data_temp3;
   A4[j]=data_temp4;
   A5[j]=data_temp5;   
}
for(i=0;i<N;i++)//the original character
{printf("%s",data[i]);
 printf("\t");
}

  printf("\n");
  gettimeofday (&tpstart1 , NULL);//get starting time
  INSERT_SORT(A1,N);
  gettimeofday (&tpend1 , NULL);//get ending time
  timeuse1=(tpend1.tv_usec-tpstart1.tv_usec)+(tpend1.tv_sec-tpstart1.tv_sec)*1000000;
  timeuse1/=1000;

  gettimeofday (&tpstart2, NULL);
  maopao(A2,N);
  gettimeofday (&tpend2, NULL);  timeuse2=(tpend2.tv_usec-tpstart2.tv_usec)+(tpend2.tv_sec-tpstart2.tv_sec)*1000000;
  timeuse2/=1000;

  gettimeofday (&tpstart3, NULL);
  QUICK_SORT(A3,0,N-1);
  gettimeofday (&tpend3 , NULL);
  timeuse3=(tpend3.tv_usec-tpstart3.tv_usec)+(tpend3.tv_sec-tpstart3.tv_sec)*1000000; 
  timeuse3/=1000;

  gettimeofday (&tpstart4, NULL); 
  MERGE_SORT(A4,0,N-1);
  gettimeofday (&tpend4 , NULL);
  timeuse4=(tpend4.tv_usec-tpstart4.tv_usec)+(tpend4.tv_sec-tpstart4.tv_sec)*1000000;
  timeuse4/=1000;
  
  gettimeofday (&tpstart5, NULL);
  HEAPSORT(A5,N-1);
  gettimeofday (&tpend5 , NULL);
  timeuse5=(tpend5.tv_usec-tpstart5.tv_usec)+(tpend5.tv_sec-tpstart5.tv_sec)*1000000;
  timeuse5/=1000;

printf("tafter insert_sort\n");
for(i=0;i<N;i++)
             printf("%s\t",A1[i]);
printf("\n");

printf("after maopao_sort:\n");
for(i=0;i<N;i++)
 printf("%s\t",A2[i]);
printf("\n");

printf("after quick_sort\n");
for(i=0;i<N;i++)
 printf("%s\t",A3[i]);
printf("\n");

printf("after merge_sort\n");
for(i=0;i<N;i++)
 printf("%s\t",A4[i]);
printf("\n");
printf("after heap_sort\n");
for(i=0;i<N;i++)
 printf("%s\t",A5[i]);
printf("\n");
printf("INSERT_SORT Timeused= %fms\n",timeuse1);//output the time used
printf("maopao_SORT Timeused= %fms\n",timeuse2);
printf("QUICK_SORT  Timeused= %fms\n",timeuse3);
printf("MERGE_SORT Timeused= %fms\n",timeuse4);
printf("HEAP_SORT Timeused= %fms\n",timeuse5);
}