Learn How Quick Sort Method WorksAlgorithm of Quick Sort
| Step 1: | LOW=FIRST HIGH=LAST |
| Step 2: | PIVOT=(LOW+HIGH)/2 |
| Step 3: | Repeat thru Step 6 while LOW<HIGH |
| Step 4: | Repeat while A[LOW]<A[PIVOT] LOW=LOW+1 |
| Step 5: | Repeat while A[HIGH]>A[PIVOT] HIGH=HIGH-1 |
| Step 6: | if (LOW<HIGH) then A[LOW] <--> A[HIGH] LOW=LOW+1 HIGH=HIGH-1 |
| Step 7: | IF(FIRST<HIGH) call QUICK_SORT(A,FIRST,HIGH) IF (LOW<LAST) call QUICK_SORT(A,LOW,LAST) |
Program of Quick Sort
#include<stdio.h>
#include<conio.h>
#define N 8
void main()
{
void quick(int *a,int first, int last);
int a[N],i,first,last;
clrscr();
printf("Enter Elements in array\n");
for(i=0;i<N;i++)
{
printf("Enter Value of A[%d]:",i);
scanf("%d",&a[i]);
}
quick(a,0,N-1);
printf("Sorted List\n");
for(i=0;i<N;i++)
{
printf("A[%d]=%d\n",i,a[i]);
}
getch();
}
void quick(int *a,int first,int last)
{
int pivot;
int low,high,temp,i;
low=first;
high=last;
pivot=(low+high)/2;
while(low<high)
{
while(a[low]<a[pivot])
low++;
while(a[high]>a[pivot])
high--;
if(low<=high)
{
temp=a[low];
a[low]=a[high];
a[high]=temp;
low++;
high--;
}
}
for(i=0;i<N;i++)
{
printf("%d ",a[i]);
}
printf("\n");
if(first<high)
quick(a,first,high);
if(low<last)
quick(a,low,last);
}