what is quick sort:-
Quick sort is one of the most efficient sorting technique because it is work on divide and conquer method.
--> the Quick sort algorithm work by partitioning the array to be sorted.
Algorithm:-
Here A is the array with N elements . Parameters BEG and END contain the boundary values of the sublist of A to which this procedure applies . LOC keeps track of the position of the first element A[BEG] of the sublist during the procedure . The local variables
LEFT and RIGHT will contain the boundary value of the list of elements that have not been scanned.
1. Set LEFT=BEG ,RIGHT=END and LOC=BEG
2. Scan from Right to Left
(a). Repeat while A[LOC]<=A[RIGHT] and LOC!=RIGHT
RIGHT=RIGHT-1
(b). If LOC==RIGHT then Return .
(c). If A[LOC]>A[RIGHT] then
(i). Interchange A[LOC] and A[RIGHT]
TEMP=A[LOC]
A[LOC]=A[RIGHT]
A[RIGHT]=TEMP
(ii). Set LOC=RIGHT
(iii). Go to step 3
3. Scan from left to right
(a). Repeat while A[LEFT]<=A[LOC] and LOC!=LEFT
LEFT=LEFT-1
(b). If LEFT==LOC then Return.
(c). If A[LEFT]>A[LOC] then
(i). Interchange A[LOC] and A[LEFT]
TEMP=A[LEFT]
A[LEFT]=A[LOC]
A[LOC]=TEMP
(ii). Set LOC=LEFT
(iii). GO to step 2
Code:-
#include<stdio.h>
int a[100];
// function for swap the values
void swap(int x,int y)
{
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}
// function for make the partition
int partition(int left,int right)
{
int loc=left;
while(left<right)
{
while(a[right]>=a[loc] && loc!=right )
right--;
if(a[loc]>a[right])
swap(loc,right);
while(a[left]<=a[loc] && loc!=left)
left++;
if(a[left]>a[loc])
swap(left,loc);
}
return loc;
}
// function for quick sort
void quick_sort(int left,int right)
{
int loc;
if(left<right)
{
loc=partition(left,right);
// calling of the quick_sort for the left side elements
quick_sort(left,loc-1);
// calling of the quick_sort for the right side elements
quick_sort( loc+1,right);
}
}
int main()
{
int n;
printf("Enter size of the array\n");
scanf("%d",&n);
printf("Enter element of the array\n");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Array before sorting :-\n");
for(int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
// function calling
quick_sort(0,n-1);
printf("Sorted array is:-\n");
for(int i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
Output:-
Enter the size of the array
5
Enter the element of the array
12 43 2 32 1
Array before sorting:-
12 43 2 32 1
Sorted array is:-
1 2 12 32 43
