/***************************************/
/*PROGRAM TO PREFORM QUICK SORT*/
/***************************************/

#include<stdio.h>
#include<conio.h>
#include<process.h>

#define SIZE 50
int quick_sort(int [],int,int);

void main()
{
       int a[SIZE],top=-1,lower[SIZE],upper[SIZE],beg,end,n,loc,i;

       clrscr();

       printf("Enter the size of array: ");
       scanf("%d",&n);
       printf("\nEnter the elements of array:\n");
       for(i=0;i<n;i++)
       {
              scanf("%d",&a[i]);
       }
       if(n>1)
       {
              top=top+1;
              lower[0]=0;
              upper[0]=n-1;
       }
       else
       {
              printf("\nNo need of sorting as there is only one element");
              getch();
              exit(1);
        }
       while(top!=-1)
       {
              beg=lower[top];
              end=upper[top];
              top=top-1;
              loc=quick_sort(a,beg,end);
              if(beg<loc-1)
             {
                     top=top+1;
                     lower[top]=beg;
                     upper[top]=loc-1;
              }
              if(loc+1<end)
              {
                     top=top+1;
                     lower[top]=loc+1;
                     upper[top]=end;
              }
       }
       printf("\nAfter sorting the elements of array are:\n");
       for(i=0;i<n;i++)
       {
              printf("%d ",a[i]);
       }
       getch();
}

int quick_sort(int a[],int beg,int end)
{
       int left,right,loc,temp;
       left=beg;
       right=end;
       loc=beg;

       again:
       while((a[loc]<=a[right])&&(loc!=right))
       {
              right=right-1;
       }
       if(loc==right)
       {
              return(loc);
       }
       if(a[loc]>a[right])
       {
              temp=a[loc];
              a[loc]=a[right];
              a[right]=temp;
              loc=right;
       }

       while((a[left]<=a[loc])&&(left!=loc))
       {
              left=left+1;
       }
       if(loc==left)
       {      
              return(loc);
       }
       if(a[left]>a[loc])
       {   
              temp=a[loc];
              a[loc]=a[left];
              a[left]=temp;
              loc=left;
       }
       goto again;
}