How to sort an array using quick sort in C
Quick sort is a way of sorting an array.
Algorithm
In quick sort, we take an element of the array called the pivot element. We then try to rearrange the array by comparing elements with the pivot element. Elements are put on the left side of the pivot element in the array if the elements are less than the pivot element. If elements are greater than the pivot element, they are put to the right of the array.
After rearranging elements to the left or right of the pivot element, consider the left side of the pivot element as one sub-array and the right side of the pivot as another sub-array. Repeat the whole process on these two subarrays (consider an element as the pivot, compare elements with the pivot, and put them to the left or right).
Repeat this process until the length of the sub-array is equal to one.
How to select the pivot element?
We can consider the first element, the middle element, or the last element as our pivot element.
Example
int a[10]={5,1,0,8,2,7,3,6,4,9};
We will consider the first element of the array as the pivot element.
Here pivot = a[0].
Consider variables i and j to iterate from thebeginning and the end
until i > j.
i should only be incremented as i = i + 1 if a[i] < pivot, so that all the elements less than the pivot are to the left of the pivot.
j should only be decremented as j = j - 1 if a[i] > pivot, so that all the elements greater than the pivot are to the right of the pivot.
while(i < j)
{
while(a[i]<=
pivot && i<=high)
i=i+1;
while(a[j]>pivot)
j=j-1;
}
While iterating, i with condition a[i]<pivot might fail, i.e, we may come across numbers larger than the pivot. Similarly, j with the a[i]>pivot condition might fail,
i.e, we may come across numbers smaller than the pivot. In such cases, we have to swap a[i] with a[j].
if(i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
When i < j condition fails, swap the pivot element with a[j].
Repeat this process for the sub-arrays till the length of the sub-arrays equals one.
Take a look at the illustration below:
Code
#include<stdio.h>int Partition(int a[],int low,int high){int i = low,j = high;int pivot = a[low],temp;while(i < j){while(a[i] <= pivot && i <= high)i = i + 1;while(a[j] > pivot)j = j - 1;if(i < j){temp = a[i];a[i] = a[j];a[j] = temp;}}a[low] = a[j];a[j] = pivot;return j;}void quicksort(int a[],int low, int high){int j,l = low,h = high;if(low < high){j = Partition(a, l, h);quicksort(a, l, j-1);quicksort(a, j+1, h);}}int main(){int low = 0,high = 10, i;int a[10]= {9,0,8,1,7,2,6,3,4,5};printf("given array elements:\n");for(i = 0;i < high;i++)printf("%d ",a[i]);quicksort(a,low, high-1);printf("\narray sorted by quick sort:\n");for(i=0;i < high;i++)printf("%d ",a[i]);return 0;}
