/*
Title: Implement Quick Sort recursively to sort the given list of numbers/ records. Display pivot position and its corresponding list in each pass.
 */

#include<stdio.h>
#include<stdlib.h>

int pass;
int accept(int a[])
{
int i,n;
printf("\nEnter no of elements: ");
scanf("%d",&n);
printf("\nEnter elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
return n;
}

void display(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("\t %d",a[i]);
}

int partition(int a[],int l,int h,int n)
{
int i,j,temp,pvt;

pvt=a[l];
i=l+1;
j=h;
while(i<=j)
{
while(a[i]<=pvt)
i++;
while(a[j]>pvt)
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
a[l]=a[j];
a[j]=pvt;
printf("\n\n\t\tPIVOT = %d",pvt);
printf("\nPASS [%d]:: ",pass++);
display(a,n);
return j;
}

void q_sort(int a[],int l,int h,int n)
{
int j;
if(l<h)
{
j=partition(a,l,h,n);
q_sort(a,l,j-1,n);
q_sort(a,j+1,h,n);
}
}


int main()
{
int a[10],n=0,ch;
while(1)
{
system("clear");
printf("\n***********MENU*************");
printf("\n1.Quick Sort\n2.Exit\nEnter ur Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
n=accept(a);
printf("\nBefore Sort: ");
display(a,n);
printf("\n");
pass=1;
q_sort(a,0,n-1,n);
printf("\n\nAfter Sort: ");
display(a,n);
getchar();
break;
case 2:
exit(0);
}
getchar();
}
return 0;
}



//END OF PROGRAM