## 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.

Pages: 1 2

### 4 Responses to “Quick Sort”

1. Quicky python solution:

def qsort(A):
if (len(A) < 2):
return A
else:
return qsort(filter(lambda x: x A[0], A[1:]))
[/sourcecode]

2. Whoops messed up the formatting.
Quicky python solution:

```def qsort(A):
if (len(A) < 2):
return A
else:
return qsort(filter(lambda x: x <= A[0], A[1:])) + [A[0]] + qsort(filter(lambda x: x > A[0], A[1:]))
```
3. Jebb said

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.

```static int swap(void *el1, void *el2, int elemSize)
{
void *buffer;
buffer = (void *)malloc(elemSize * sizeof(char));
assert(buffer);
memcpy(buffer, el1, elemSize);
memcpy(el1, el2, elemSize);
memcpy(el2, buffer, elemSize);
free(buffer);
}

static int partition(void *base, int length, int elemSize, void *pivot,
int (*cmpFunc)(void *, void *))
{
int i, newIndex;
void *elt1, *elt2, *lastElt;
lastElt = (char *)base + (length - 1) * elemSize;
swap(pivot, lastElt, elemSize); //Move the pivot out of the way
newIndex = 0;
elt1 = base;
for (i = 0; i < length - 1; i++) {  //We're storing the pivot at the end!!!
elt2 = (char *)base + i * elemSize;
if (cmpFunc(lastElt, elt2) < 0) {
swap(elt1, elt2, elemSize);
newIndex++;
elt1 = (char*)base + newIndex * elemSize;
}
}
/*Now we only need to re-insert the pivot (which we've stored at lastElt)
*in the array at the proper index
*With the numbering used, newIndex is now the index of the first element
*"larger" than the pivot
*elt1 is still the array element of index newIndex*/
swap(lastElt, elt1, elemSize);
return newIndex;
}

int quisort(void *base, int length, int elemSize, int (*cmpFunc)(void *, void *))
{
int pivotNewIndex;
void *pivot, *base2;
if (length > 1) {
srand(time(0));
pivot = (char *)base + (rand() % length) * elemSize;
pivotNewIndex = partition(base, length, elemSize, pivot, cmpFunc);
base2 = (char *)base + (pivotNewIndex + 1) * elemSize;
quisort(base, pivotNewIndex, elemSize, cmpFunc);
quisort(base2, length - pivotNewIndex - 1, elemSize, cmpFunc);
}
return 0;
}```
4. Vikas Tandi said

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

```#include <stdlib.h>
#include <time.h>

#define M 10

void insertion_sort(int arr[], int left, int right);
static void swap(int arr[], int i, int j);
static int partition(int arr[], int left, int right);
static void quicksort_imp(int arr[], int left, int right);

/* assume presence of two artificial keys arr[0] = -ve infinity
and arr[n+1] = +ve infinity such that arr[0] <= arr[i] <= arr[n+1]
for 1 <= i <= n */
void quicksort(int arr[], int left, int right)
{
/* if array size is small or equal to M than
sort it directly by straight insertion sort */
if((right-left-1) > M)
quicksort_imp(arr, left+1, right-1);

if(M > 1)
insertion_sort(arr, left+1, right-1);
}

static void quicksort_imp(int arr[], int left, int right)
{
int pivot, mid;

/* select pivot element */
mid = (left + right)/2;
pivot = (left + mid + right)/3;

/* swap pivot element with the first element */
swap(arr, left, pivot);

/* partition the array */
pivot = partition(arr, left, right);

/* right subfile is greater than or equal to left subfile and both subfiles are greater than M */
if((right - pivot) >= (pivot - left)	&&
(right - pivot) > M					&&
(pivot - left) > M)
{
/* sort the smaller subfile first to ensure that the stack size doesn't grow
more than log N */
quicksort_imp(arr, left, pivot-1);
quicksort_imp(arr, pivot+1, right);
}

/* left subfile is greater than right subfile and also both subfiles are greater than M */
if((pivot - left) > (right - pivot) 	&&
(right - pivot) > M					&&
(pivot - left) > M)
{
/* sort the smaller subfile first to ensure that the stack size doesn't grow
more than log N */
quicksort_imp(arr, pivot+1, right);
quicksort_imp(arr, left, pivot-1);
}

/* right subfile is greater than left subfile, right subfile is greater than M
and left subfiles is less than or equal to M */
if((right - pivot) > (pivot - left)	&&
(right - pivot) > M				&&
(pivot - left) <= M)
{
quicksort_imp(arr, pivot+1, right);
}

/* left subfile is greater than right subfile, left subfile is greater than M
and right subfiles is less than or equal to M */
if((pivot - left) > (right - pivot)	&&
(pivot - left) > M				&&
(right - pivot) <= M)
{
quicksort_imp(arr, left, pivot-1);
}

/* if both subfile are smaller than M, unwind the stack */
}

static int partition(int arr[], int left, int right)
{
int i, j, key;

/* partition the element */
for(i = left, j = right+1, key = arr[left]; ;)
{
/* compare key with arr[i] */
for(i = i+1; arr[i] < key; i++);		/* the loop must terminate with i <= j as arr[j] >= key */

/* compare key with arr[j] */
for(j = j-1; arr[j] > key; j--);		/* the loop must terminate with j >= (i-1) as arr[i-1] <= key */

if(j <= i)	/* end of partition */
{
swap(arr, left, j);
break;
}
swap(arr, i, j);
}

return j;
}

void insertion_sort(int arr[], int left, int right)
{
int i, min;

/* move smallest key to left end */
for(i = left+1, min = left; i <= right; i++)
if(arr[min] > arr[i])
min = i;

swap(arr, left, min);

for(i = left+1; i <= right; i++)
{
int j, key;

for(j = i-1, key = arr[i]; arr[j] > key; j--)
arr[j+1] = arr[j];

arr[j+1] = key;
}
}

static void swap(int arr[], int i, int j)
{
int t;
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
```