Quick sort is one of the fastest sorting algorithms known. It sorts O(n log n) in the average case while sorts O(n2) in the worst case. But in practice, it’s quick because the worst case doesn’t happen often. This based on divide-and-conquer strategy. It takes an array A that is to be sorted. The array A[p..r] is then partitioned into two non-empty sub-arrays A[p..q] and A[q+1..r] where q is somewhere between p and r. All elements in A[p..q] are less than all elements in A[q+1..r]. The sub-arrays are recursively sorted by calls to quicksort algorithm. Unlike merge sort, there is no combining step. The two sub-arrays form an already-sorted array.

Quicksort Algorithm

Quicksort(A, p, r)
    if (p < r)
        q = Partition(A, p, r);
        Quicksort(A, p, q);
        Quicksort(A, q+1, r);

Clearly, all the action takes place in the partition() function. It rearranges the sub-array in place. The end result is two sub-arrays and all values in first sub-array are smaller than all values in second. Partition function returns the index of the “pivot” element separating the two sub-arrays.

Partition(A, p, r) {
 x = A[p]
 q = p
 for(s=p+1 to r) {
   if(A[s] < x){
     q = q + 1;
 return q;


Graphical Explanation of Partition Function

Graphical Explanation of Quick Sort

What will be the worst case for the algorithm?

Partition is always unbalanced

What will be the best case for the algorithm?

Partition is perfectly balanced

Will any particular input elicit the worst case?

Yes, Already-sorted input

The real liability of Quicksort is that it runs in O(n2) on already-sorted input. There could be two possible solutions to avoid this problem:

  • Randomize the input array, OR
  • Pick a random pivot element

This will ensure that no particular input can be chosen to make Quicksort run in O(n2) time.

Tagged with: C/C++ language

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.