7. Quick Sort

/* Title : Quick Sort */



/* header files */
#include<stdio.h>
#include<conio.h>

 int main(void)
{
int a[50], n=0, ch=0, temp=0;

void accept(int [], int);
void display(int [], int);
int quicksort(int [], int, int, int, int);

clrscr();

do
{
printf("\n\n\tMenu");
printf("\n1 : Accept");
printf("\n2 : Display");
printf("\n3 : Quicksort");
printf("\n4 : Exit");
printf("\nEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1 : printf("\nEnter the no. of elements :");
scanf("%d",&n);
printf("\nEnter the elements : ");
accept(a,n); /* Function call */
break;

case 2 : printf("\nThe elements of array are : ");
display(a,n);
break;

case 3 : printf("\nQuick Sort is:-");
temp=quicksort(a,0,n-1,n,0);
printf("\n\nSorted array is : ");
display(a,n);
printf("\n\nNo. of passes : %d",temp);
break;
}
}
while(ch<=3&&ch!=0);

getch();
return 0;
}

void accept(int a[50],int n) /* Function definition */
{
int i=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}

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

int quicksort(int a[],int l,int u,int n,int passes)
{
int j=0;
if(l<=u)
{
passes++;
j=partition(a,l,u,n,passes); /*j=pivoted point*/
quicksort(a,l,j-1,n,passes); /*range of elemnets to be sorted*/
quicksort(a,j+1,u,n,passes); /*range of elemnets to be sorted*/

}
passes++;
return (passes);

}


int partition(int a[],int l,int u,int n,int passes)
{
int v=0, i=0, j=0, temp=0;

v=a[l];
i=l;
j=u+1;
do
{
do
{
i++;
}
while(a[i]<v&&i<u);

do
{
j--;
}
while(v<a[j]);

if(i<j) /* conditon for swap */
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}

}
while(i<j);

printf("\nresult after pass %d : ",passes);
display(a,n);

a[l]=a[j];
a[j]=v;
return(j);
}