How does Quicksort work?

Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern.

Quick sort works as follows.

A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.

At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.

Here partition process is the key to sorting.

Consider the following example to understand the partitioning process.

Initial array: 4 is chosen as pivot for simplicity

After partitioning:

You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).

Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.

#include <iostream>

using namespace std;

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

int main()
{
 int array[] = {4,7,3,6,9,2,8,5,1};
 quick_sort(array,0,8);
 for( int i = 0; i < 9; i++ )
 {
  cout<<array[i]<<" ";
 }
 
 return 0;
}

void quick_sort(int array[], int l, int h)
{
 if( l < h)
 {
  int left = l; //starting index of the array
  int right = h;// ending index of the array
  int pivot = array[left];//take left most element as pivot
  
  while ( left < right)
  {
   //decrement right pointer as long as the element
   //at this index is greater than pivot
   while ( array[right] > pivot )
    right--;
   //increment left pointer as long as the element
   //at this index is less than or eqal to pivot
   while ( array[left] <= pivot )
    left++;
   
   //swap the elements if left and right do not overlap
   if( left < right)
   {
    swap( array[left], array[right] );
   }
  }
  
  //right is the correct position for pivot,
  //so swap the first element(chosen as pivot) with 'right'
  swap(array[l],array[right]); 
  
  //recursively call quick sort for left and right parts
  quick_sort(array, l, right-1);
  quick_sort( array, right+1,h);
  
 }
}

Leave a Reply Cancel reply