Quick Sort

This quick sort implementation comes from ‘Programming Pearls’ by Jon Bentley. The basic idea of quick sort is ‘divided and conquer’.

  1. Choose the pivot
  2. Partitioning the array to have half the elements are above the pivot and half the elements are below it.
  3. Repeat for each partition till partitions have one element

The code is

void qsort(l, u)
  if l >= u then
    /* at most one element, do nothing */
    return
  /* goal: partition array around a particular value(pivot),
     which is eventually placed in its correct position p
  */
  qsort(l, p-1)
  qsort(p+1, u)

In quicksort we’ll partition the array x[l..u] around the value t=x[l]. In the below pseudo code, m-th element indicates the right most element which is less than pivot value. It starts from l+1 because l-th element is the pivot. When we find the i-th element which has the value less than pivot, we swap it with ++m-th element which is left most element greater or equal to pivot.

void qsort(l, u)
  if (l >= u)
    return
  m = l
  for i = [l+1, u]
    /* invariant: x[l+1..m]    < x[i] &&
                  x[m+1..i-1] >= x[l] */
    if(x[i] < x[l])
      swap(++m, i)
  swap(l, m)
  /* x[l..m-1] < x[m] <= x[m+1..u] */
  qsort(l, m-1)
  qsort(m+1, u)

When iterating in for loop the partitions are depicted as

image

m indicates the right most element smaller than pivot. When the loop terminates we have

image

We then swap x[l] with x[m] to give

image

Lets say we have the input array x = {12, 3, 20, 8, 19, 21, 7}. After terminating the for loop, x will be x = {7, 3, 8, 12, 19, 21, 20}.

x[l]=12 m=0
i=1, 3<12 ? yes, m=1, swap(1,1)
i=2, 20<12 ? no
i=3, 8<12 ? yes, m=2, swap(2,3), x={12,3,8,20,19,21,7}
i=4, 19<12 ? no
i=5, 21<12 ? no
i=6, 7<12 ? yes, m=3, swap(3,6), x={12,3,8,7,19,21,20}
swap(0,3), x={7,3,8,12,19,21,20}

The quicksort runs in O(n log n) time and O(log n) stack space on the average.


[1] Programming Pearls 2nd ed, Jon Bentley
[2] https://stackoverflow.com/questions/10049579/jon-bentleys-beautiful-quicksort-how-does-it-even-work

Advertisements
This entry was posted in Algorithms, Technical Interview and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s