#include<stdio.h>
 
void partiton(int A[],int,int);
 
void main()
{
 int A[45],q,i;
 printf("Enter the number of elements in the Array: ");
 scanf("%d",&q);
 
 for(i=0 ; i<q ; i++)
 {
  printf(" Array[%d] = ",i);
  scanf("%d",& A[i]);
 }
 
 partition(A,0,q-1);
 printf("\nThe Sorted Array is:\n\n");
 
 for(i=0 ; i<q ; i++)
 {
  printf(" %4d",A[i]);
 }
 getch();
}
 
void partition(int A[],int p,int r)
{
 int xchg,j,temp,i;
 if(p<r)
 {
  xchg = p;
  i = p;
  j = r;
 
  while(i<j)
  {
   while((A[i]<=A[xchg])&&(i<r))
   {
    i++;
   }
 
   while(A[j]>A[xchg])
   {
    j--;
   }
 
   if(i<j)
   {
    temp=A[i];
    A[i]=A[j];
    A[j]=temp;
   }
  }
 
  temp=A[xchg];
  A[xchg]=A[j];
  A[j]=temp;
  partition(A,p,j-1);
  partition(A,j+1,r);
 }
}