### Ticker

6/recent/ticker-posts

# c program and algorithm of quick sort

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