Quick Sort Algorithm in C


Quick Sort algorithm is algo. for sorting given no of data with complexity 'in order of' n2[O(n2)].Here is the complete program Implemented in C language for Microsoft Windows OS.



#include
#include
void sort(int [],int,int);  //prototype of sort()
void partarray(int [],int,int,int *);  // prototype of partition()
void main()
{
 int i,j,a[8]={13,24,324,41,55,46,37,38};   
 clrscr();
 sort(a,0,7);// call to sort function
                   //0 points to lower bound
    // 7 points to upper bound
 for(i=0;i<8;i++)
  printf("%d\n",a[i]);  //printing sorted array
 getch();
}
void sort(int a[],int lb,int ub)
{
 int j;
 if(lb >=ub)      // condition for recursion breaking 
  return;
 partarray(a,lb,ub,&j);
 sort(a,lb,j-1);         //recursive call to sort() function
 sort(a,j+1,ub);
}
void partarray(int a[],int lb,int ub,int *j)
{
 int b,down,up,t; //if you see,left most end is 
                         // pointed by up pointer and
                         // vice versa
 b=a[lb];
 down=ub;
 up=lb;
 while(down > up)
 {
  while(a[up] <= b && up < ub)
   up++;    //updating up pointer
  while(a[down] > b && down >= lb)
   down--;  //uadating down pointer
  if(down > up)
  {
   t=a[down];
   a[down]=a[up];
   a[up]=t;
  }

 }
 a[lb]=a[down];
 a[down]=b;
 *j=down;
}
Protected by Copyscape Web Plagiarism Detector

You can also analyze the time taken by sort() function in Linux OS using 'gettimeofday()' function.


Ads: ebay :ebay UK Best selling and shopping at:ebay ebay.co.uk

See Also:

No comments:

Post a Comment