Quick Sort
QUICK SORT IN C
Back to Quick SortQuick Sort is another sorting algorithm that is based on divide and conquer approach. Unlike merge sort that divides input elements according to their position in array, quick sort divides input element according to their values. Here is a three-step divide and conquer process for sorting a typical sub-array.
Need Python Homework Help: Get Python Homework Help from Epert
Divide : Partition or rearrange the array a[p . . r] into two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] such that a[ p . . q-1 ] <= a[q] <= a[q+1 . . r] . Compute the index q as part of this partition procedure. Here a[q] is called the pivot element.
Conquer : Sort the two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] by recursive calls to quick sort.
Combine : Because the sub-arrays are already sorted, no work is needed to combine them : the entire array a[ p . . r ] is now sorted.
Lets understand Quick Sort with the help of an example :
Array Elements ( List ) : 2 8 7 1 3 5 6 4
Steps :
Array Elements ( List ) : 2 8 7 1 3 5 6 4
Steps :
- Select the pivot element ( 4 in this case )
- Rearrange elements such that elements before pivot element are less than it and element after pivot element are greater than it. This arrangement of elements in accordance with the pivot element is called partition operation.
- Sort the sub-array recursively.
![]() |
Steps for Quick Sort |
QUICK SORT ALGORITHM
// Algorithm for Quick Sort
QUICKSORT(a, p, r)
if p<r
q = PARTITION(a, p, r)
QUICKSORT(a, p, q-1)
QUICKSORT(a, q+1, r)
Partitioning the array :
PARTITION(a, p, r)
x=a[r]
i=p-1
for j=p to r-1
if(a[j]<=x)
i=i+1
swap a[i] with a[j]
end loop
swap a[i+1] with a[r]
return i+1
QUICK SORT PROGRAM IN C
//Quick sort program ( code ) in c
#include<stdio.h>
void quicksort(int a[],int p, int r);
int partition(int a[],int p, int r);
int main()
{
int a[20],i,n;
printf("Enter number of elements in array : ");
scanf("%d",&n);
// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}
// Displaying Elements before quick sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
//Applying quick sort
quicksort(a,0,n-1);
// Displaying elements after quick sort
printf("\nElements after quick sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
void quicksort(int a[],int p, int r)
{
int q;
if(p<r)
{
// q - index at which pivot element lies
q=partition(a,p,r);
// Sorting sub-array recursively
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int partition(int a[],int p, int r)
{
int temp;
int i=p-1;
int j;
// pivot element around which partition is done
int x=a[r];
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return (i+1);
}
Quick Sort Program Output
![]() |
Quick Sort : Quick Sort Program Output |
More Informative Posts :
- Counting Sort Program In C
- Heap Sort Program In C
- Merge Sort Program In C
- Bubble Sort Program In C
- Selection Sort Program In C
- Insertion Sort Program In C
- Shell sort Program In C
- Radix Sort Program In C
- Bucket Sort Program In C