Quick Sort

 

#include<stdio.h>

#include<unistd.h>

#include<stdlib.h>

#include<time.h>

 

 

void swap(int *a ,int *b)

{

int x=*a;

*a=*b;

*b=x;

}

 

int getpivote(int *a,int left,int right)

{

int middle=(left+right)/2;

if(a[left]>a[middle])

swap(&a[left],&a[middle]);

if(a[left]>a[right])

swap(&a[left],&a[right]);

if(a[middle]>a[right])

swap(&a[middle],&a[right]);

swap(&a[middle],&a[right-1]);

return a[right-1];

 

 

 

}

 

 

void quicksort(int *a,int left,int right)

{

if(left<right)

{

int pivote=getpivote(a,left,right);

int i=left;

int j=right-1;

while(1)

{

while(a[++i]<pivote);

while(a[--j]>pivote);

if(i<j)

 

swap(&a[i],&a[j]);

else

break;

}

swap(&a[i],&a[right-1]);

quicksort(a,left,i-1);

quicksort(a,i+1,right);

 

 

 

}

 

 

 

 

}

 

 

int main()

{

 

 

int *a,n,i;

printf("\n Enter The size of the Data To Sort\n");

scanf("%d",&n);

a=(int *)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

a[i]=rand()%(n+1);

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

quicksort(a,0,n);

gettimeofday(&tv_end,NULL);

 

printf("\n shyam\n");

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n---------------------\n Time Taken is %g \n",((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)*0.000001));

return 0;

}