## Quick Sort

### November 3, 2009

We will provide four quick sorts of increasing sophistication, beginning with this simple quicksort based on Lomuto’s partition:

`function swap(A,i,j, t) {`

t = A[i]; A[i] = A[j]; A[j] = t }

`function qsort(A,lo,hi, i,last) {`

if (lo >= hi)

return

swap(A, lo, lo + int((hi-lo+1) * rand()))

last = lo

for (i=lo+1; i<=hi; i++)

if (A[i] < A[lo])

swap(A, ++last, i)

swap(A, lo, last)

qsort(A, lo, last-1)

qsort(A, last+1, hi) }

`function sort(A,n) { qsort(A, 1, n) }`

Our second version moves swaps inline and eliminates recursion; *lo* and *hi* are the endpoints of the current sort range, *i* and *j* are pointers to elements of the array, *t* is a temporary value, *s* is the recursion stack that stores the previous *lo* and *hi* values in each frame, and *p* is a pointer to the stack:

`function sort(A,n, lo,hi,i,j,t,s,p) {`

lo = 1; hi = n; p = 2

do {

if (hi > lo) {

j = lo + int((hi - lo + 1) * rand())

t = A[lo]; A[lo] = A[j]; A[j] = t

j = lo

for (i=lo+1; i<=hi; i++)

if (A[i] < A[lo]) {

j++; t = A[j]; A[j] = A[i]; A[i] = t }

t = A[lo]; A[lo] = A[j]; A[j] = t

if ((j - lo) < (hi - j)) {

s[p] = lo; s[p+1] = j - 1; lo = j + 1 }

else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }

p += 2 }

else { p -= 2; lo = s[p]; hi = s[p+1] }

} while (p > 0) }

Much of the time spent in quick sort is wasted in the recursive calls for small sub-arrays, which involve more pushing and popping the stack than comparing and exchanging array elements. A common fix is to *almost*-sort the array, leaving small sub-arrays unsorted, then finish the sort by calling insert sort, which is very fast on arrays that are nearly sorted:

`function sort(A,n, lo,hi,i,j,t,s,p) {`

lo = 1; hi = n; p = 2

do {

if (hi - lo > 10) {

j = lo + int((hi - lo + 1) * rand())

t = A[lo]; A[lo] = A[j]; A[j] = t

j = lo

for (i=lo+1; i<=hi; i++)

if (A[i] < A[lo]) {

j++; t = A[j]; A[j] = A[i]; A[i] = t }

t = A[lo]; A[lo] = A[j]; A[j] = t

if ((j - lo) < (hi - j)) {

s[p] = lo; s[p+1] = j - 1; lo = j + 1 }

else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }

p += 2 }

else { p -= 2; lo = s[p]; hi = s[p+1] }

} while (p > 0)

for (i=2; i<=n; i++) {

t = A[i]

for (j=i; j>1 && A[j-1] > t; j--)

A[j] = A[j-1]

A[j] = t } }

Our final version of quick sort uses the very fast approaching-pointers partition; beware the details:

`function sort(A,n, lo,hi,i,j,t,v,s,p) {`

lo = 1; hi = n; p = 2

do {

if (hi - lo > 10) {

i = lo + int((hi - lo + 1) * rand())

t = A[lo]; A[lo] = A[i]; A[i] = t

j = lo + int((hi - lo + 1) * rand())

t = A[hi]; A[hi] = A[j]; A[j] = t

if (A[hi] < A[lo]) {

t = A[lo]; A[lo] = A[hi]; A[hi] = t }

v = A[hi]; i = lo; j = hi

do {

do { i++ } while (A[i] < v)

do { j-- } while (v < A[j])

t = A[i]; A[i] = A[j]; A[j] = t

} while (i < j)

t = A[i]; A[i] = A[hi]; A[hi] = t

if ((i - lo) > (hi - i)) {

s[p] = lo; s[p+1] = i - 1; lo = i + 1 }

else { s[p] = i + 1; s[p+1] = hi; hi = i - 1 }

p += 2 }

else { p -= 2; lo = s[p]; hi = s[p+1] }

} while (p > 0)

for (i=2; i<=n; i++) {

t = A[i]

for (j=i; j>1 && A[j-1] > t; j--)

A[j] = A[j-1]

A[j] = t } }

Quick sort has time complexity *O*(*n* log n) unless the data is such that the random choice of pivot is near the ends of the sub-array at each partitioning step. If you are worried about the quadratic worst-case performance, Jon L. Bentley and M. Douglas McIlroy give a solution in their classic 1993 *Software—Practice and Experience* paper “Engineering a Sort Function” (Volume 23, Number 11, pages 1249–1265).

The code, including the test suite of the previous exercise, is collected at http://programmingpraxis.codepad.org/wTUyljFX, but you can’t run it, since codepad doesn’t provide an Awk interpreter.

Quicky python solution:

def qsort(A):

if (len(A) < 2):

return A

else:

return qsort(filter(lambda x: x A[0], A[1:]))

[/sourcecode]

Whoops messed up the formatting.

Quicky python solution:

Ongoing experimentations in C. I’d implemented an integer version of this a few months ago, and I just went back and generalized it now I’ve learned how function pointers and (void *) passing works.

generating random every is very costly and slows down the algorithm considerably.

I have used the median of three elements instead.

Here is my c implementation