Quicksort algorithm

Explain the algorithm for QUICK sort ( partition exchange sort) and give a suitable example.

Quicksort is based on partition. It is also known as partition exchange sorting. The basic concept of quicksort process is picking one element from an array and rearranges the remaining elements around it. This element divides the main list into two sublists. This chosen element is called the pivot. Once pivot is chosen, then it shifts all the elements less than pivot to the left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.

Implementation of Quick sort in C language:

#include<stdio.h>

void quicksort(int[ ],int,int);

int main( )

{

int low, high, pivot, t, n, i, j, a[10];

printf("\nHow many elements you want to sort ? \n ");

scanf("%d",&n);

printf("\nEnter elements for an array:\n");

for(i=0; i<n; i++)

{

printf("a[%d] = ",i);

scanf("%d",&a[i]);

printf("\n");

}

low=0;

high=n-1;

quicksort(a,low,high);

printf("\nAfter Sorting the elements are:\n");

for(i=0;i<n;i++)

printf("%d ",a[i]);

return 0;

}

void quicksort(int a[ ],int low,int high)

{

int pivot,t,i,j;

if(low<high)

{

pivot=a[low];

i=low+1;

j=high;

while(1)

{

while(pivot>a[i]&&i<=high)

i++;

while(pivot<a[j]&&j>=low)

j--;

if(i<j)

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

else

break;

}

a[low]=a[j];

a[j]=pivot;

quicksort(a,low,j-1);

quicksort(a,j+1,high);

}

}

The program output is tested on www.jdoodle.com

Output:

How many elements you want to sort ? 

 6

Enter elements for an array:

a[0] = 2

a[1] = 4

a[2] = 6

a[3] = 8

a[4] = 7

a[5] = 5

After Sorting the elements are:

2 4 5 6 7 8 

Thanks

Mukesh Rajput