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

- Choose the pivot
- Partitioning the array to have half the elements are above the pivot and half the elements are below it.
- 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

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

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

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

### Like this:

Like Loading...

*Related*