Quick Sort Program

1. Sort a given set of elements using the Quicksort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

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

void quicksort(int,int);
int partition(int,int);
void interchange(int,int);

int a[10000000];

void main()
{
 int i,n;
 clock_t start,end;
 printf("\n\n********QUICK SORT PROGRAM*****\n\n");
 printf("Enter the number of elements to be sorted \n");
 scanf("%d",&n);
 for(i=0;i<n;i++) a[i]=rand()%100;
 printf("\n Array elements to be sorted are\n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 a[n]=999;
 start=clock();
 quicksort(0,n-1);
 end=clock();
 printf("\n\n The sorted elements are\n");for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 printf("\n\n The time taken is %f \n",(double)(end-start)/CLOCKS_PER_SEC);
 printf("\n*********\n\n");
}
 void quicksort(int p,int q)
 {
  int j;
  if(p<q)
   {
    j=partition(p,q);
    quicksort(p,j-1);
    quicksort(j+1,q);
   }
 }
int partition(int p,int q)
{
 int v,i,j;
 v=a[p];
 i=p;
 j=q;
 while(i<=j)
 {
  while(a[i]<=v)i++;
  while(a[j]>v)j--;
  if(i<j)
  interchange(i,j);
 }
 a[p]=a[j];
 a[j]=v;
 return j;
}
void interchange(int i,int j)
{
 int p;
 p=a[i];
 a[i]=a[j];
 a[j]=p;
}



OUTPUT:

Enter the number of elements to be sorted
6

Array elements to be sorted are
83  86  77  15  93  35