In this tutorial you will learn about algorithm and program for quick sort in C.

Quick sort is the fastest internal sorting algorithm with the time complexity O (n log n). The basic algorithm to sort an array a[ ] of n elements can be described recursively as follows:

## Quick Sort Algorithm

1. If n < = 1, then return.

2. Pick any element V in a[]. This is called the pivot.

3. Rearrange elements of the array by moving all elements xi > V right of V and all elements xi < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].

4. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

## Quick Sort Animation

Visualization of the quicksort algorithm. The horizontal lines are pivot values.

## Quick Sort Program in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <stdio.h> void quick_sort(int[],int,int); int partition(int[],int,int); int main() { int a[50],n,i; printf("How many elements?"); scanf("%d",&n); printf("\nEnter array elements:"); for(i=0;i<n;i++) scanf("%d",&a[i]); quick_sort(a,0,n-1); printf("\nArray after sorting:"); for(i=0;i<n;i++) printf("%d ",a[i]); return 0; } void quick_sort(int a[],int l,int u) { int j; if(l<u) { j=partition(a,l,u); quick_sort(a,l,j-1); quick_sort(a,j+1,u); } } int partition(int a[],int l,int u) { int v,i,j,temp; v=a[l]; i=l; j=u+1; do { do i++; while(a[i]<v&&i<=u); do j--; while(v<a[j]); if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } }while(i<j); a[l]=a[j]; a[j]=v; return(j); } |

If you found anything incorrect or have any doubts regarding above quick sort in C tutorial then comment below.

sadia julekhacan anyone make me understand the implementation of quicksort?

SambasivaRaosimple programming,easy to understand.

thank you bro.

YadavHow to calculate time and space complexity in code?

sivabalahi boss can you explain in detail manner how the quick sort is working ?

Neeraj Mishraofc but first stop calling me boss

call me handsome instead

facts>fiction

Devendra PrajapatiIf i want to Enter 100 or MORE Number then……

_____

User Want Enter Any Number so..

What he/she will do??

SirishaSir,

you have to return the array in order to print it the array after sorting.And we should sort the key as well i.e,pivot element

So the j in the calling of quicksort equals to j in any of the call

SHreyaI seriously love the animation part, which makes it more interesting to see the content.

And Sir, you program’s are so, accurate and efficient.

Thank you for providing us this website and helping new coder like me, to get to know, what exactly is a GOOD CODE to approach.

You are seriously doing a good job.

Thank you.

sayemyes,u r right shreya

Haniavoid quick_sort(int a[],int l,int u)

{

int j;

if(l<u)

{

j=partition(a,l,u);

quick_sort(a,l,j-1);

quick_sort(a,j+1,u);

}

can anyone explain this??

pushpa polumuruWhen you take a pivot element and sort all the elements based on that,u need to call quick sort for left group and right group.J is pivot element so here we are calling quicksort for left and right.

JanieBiggieHi admin, i’ve been reading your page for some time and I really like coming back

here. I can see that you probably don’t make money

on your page. I know one interesting method of earning

money, I think you will like it. Search google for:

dracko’s tricks

puneet vermaSir I just love your content. Keep it up. Wish i could meet you in person and share a hug.

akshaya jint partition(int a[],int l,int u)

{

int v,i,j,temp;

v=a[l];

i=l;

j=u+1;

do

{

do

i++;

while(a[i]<v&&i<=u);

do

j–;

while(v<a[j]);

if(i<j)

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}while(i<j);

a[l]=a[j];

a[j]=v;

can any one explain me this?

YashThe sorted array is not displaying

AdarshWe known that their is no keyword to define the array.

Phil GerringI believe partition() has an error. In this loop, it is possible to access a[i] where i > u:

do

{

i++;

}

while(a[i]<v&&i<=u);

On the first call to partition, when u will usually be equal to the last valid index for a[], we will attempt to access memory beyond the array's upper bound. This may crash the program. The solution is simply to reverse the order of the operands in the test:

do

{

i++;

}

while(i<=u&&a[i]<v);

Nileshits very useful blog

Dip RoyI think the first do – while block should compare against:

} while( array[i] < v && i < u);

AnkitHey admin, how you got execution time here?

I can’t see any as such

Rishitause codeblocks compiler!!

dhinaError found like this ” ) expected ” line 20

namandeepawesome cocept

Nancy ChoudharyHow to reverse the sorted elements in reverse order