Quick Sort

Quick Sort
Worst case = theta (n2)
average case thete(nlogn)
It works on divide and conquer strategy.
Divide an array A[p...r] in A[p....q-1] and A[q+1....r] such that each element in A[p...q-1] is less than A[q] and those in A[q+1...r] are greater than A[q].
Sort the two subarrays recursively.
Pivot element is chosen against which comparisons are made and two regions are maintained which contain elements less than the pivot element and other region contains elements greater than it. At last pivot element is swapped with the element at the position next to region 1.


Try following code snippet:

#include<stdio.h>
#define MAX_SIZE 10
 void Quick_sort(int *a,int p, int r);
  int Partition(int *a,int start,int end);
void main()
{
 int arr[MAX_SIZE];
 int i,pos;

 for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n enter the element : : %d ",i+1);
  scanf("%d",&arr[i]);
 }

 Quick_sort(arr,0,MAX_SIZE-1);
  for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n element %d",arr[i]);
 }
  getchar();
  getchar();

}

void Quick_sort(int *a,int p, int r)
 {
     int index;
     if(p<r)
     {
        index=Partition(a,p,r);
         Quick_sort(a,p,index-1);
         Quick_sort(a,index+1,r);
     }
 }

 int Partition(int *A,int start,int end)
 {
int x=A[end];
int i =start-1;
int temp;
for(int j=start;j<end;j++)
{
  if(A[j]<=x)
     {
  i=i+1;
temp=A[i];
A[i]=A[j];
A[j]=temp;

}
}
temp=A[i+1];
A[i+1]=A[end];
A[end]=temp;
return i+1;
 }