Wikipedia contains a C language implementation of QuickSort which looks like this: [UPDATE: Wikipedia’s content is constantly shifting, and is no longer accurately reflected by the following code sample. Also, Jiri Horky has notified me that the below code contains a couple of errors. It was captured in August 2005, but Wikipedia doesn’t seem to go back that far. Their October 2005 version includes Horky’s fixes.]

void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; } void sort(int arr[], int beg, int end) { if (end > beg + 1) { int piv = arr[beg], l = beg + 1, r = end; while (l < r) { if (arr[l] <= piv) l++; else swap(&arr[l], &arr[--r]); } swap(&arr[--l], &arr[beg]); sort(arr, beg, l); sort(arr, r, end); } } |

This Wiki code is closely replicated on many other sites, and probably in many in-use implementations. I have rewritten it here to execute more efficiently, as follows:

// quickSort // // This public-domain C implementation by Darel Rex Finley. // // * Returns YES if sort was successful, or NO if the nested // pivots went too deep, in which case your array will have // been re-ordered, but probably not sorted correctly. // // * This function assumes it is called with valid parameters. // // * Example calls: // quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4 // quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7 bool quickSort(int *arr, int elements) { #define MAX_LEVELS 1000 int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ; beg[0]=0; end[0]=elements; while (i>=0) { L=beg[i]; R=end[i]-1; if (L<R) { piv=arr[L]; if (i==MAX_LEVELS-1) return NO; while (L<R) { while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; } arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; } else { i--; }} return YES; } |

Advantages of my code over the Wikipedia code:

1.

2.

3.

4.

5.

6.

(Note that the benefits of all six advantages are greatly increased if the items being sorted are substantially sized data structures, as opposed to simple integers as in these code examples.)

Limitations of my code vs. the Wiki code:

1.

Both functions seem to do about the same number of increments/decrements, as far as I can tell.

Here’s an example of how my code handles one pivot round (a.k.a. “partition”):

piv |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
||

? | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | Starting condition. | |

Copy first item to pivot stash. | ||||||||||

4 | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | ||

Set L and R to the span of the partition. | ||||||||||

Decrement R until it finds an item that is less than the pivot value. | ||||||||||

Copy that item to position L. | ||||||||||

4 | 1 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | ||

Increment L until it finds an item that is more than the pivot value. | ||||||||||

Copy that item to position R. | ||||||||||

4 | 1 | 5 | 3 | 6 | 2 | 8 | 5 | 7 | ||

Decrement R until it finds an item that is less than the pivot value. | ||||||||||

Copy that item to position L. | ||||||||||

4 | 1 | 2 | 3 | 6 | 2 | 8 | 5 | 7 | ||

Increment L until it finds an item that is more than the pivot value. | ||||||||||

Copy that item to position R. | ||||||||||

4 | 1 | 2 | 3 | 6 | 6 | 8 | 5 | 7 | ||

Decrement R — now L is not less than R, so... | ||||||||||

...copy the pivot to position L. | ||||||||||

4 | 1 | 2 | 3 | 4 | 6 | 8 | 5 | 7 | Done! | |

piv |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |

Notice that the data values 3, 8, and 7 (in slots [2], [5], and [7], respectively) do not move because they don’t need to. All other items (except the pivot) are moved only once, and each item is compared with the pivot only once.

Now — here’s how the Wiki code handles the same pivot round. (I will assume that the programmer has the good sense to declare the “swap” function “inline”, so that there is no function-call overhead during the processing of a pivot round.)

piv |
T |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
|||

? | ? | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | Starting condition. | ||

Copy first item to pivot stash. | ||||||||||||

4 | ? | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | |||

Initialize L and R. | ||||||||||||

Increment L until it finds an item larger than the pivot. | ||||||||||||

Decrement R. | ||||||||||||

Swap items L and R through swap var T. | ||||||||||||

4 | 5 | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | |||

4 | 5 | 4 | 7 | 3 | 6 | 2 | 8 | 1 | 7 | |||

4 | 5 | 4 | 7 | 3 | 6 | 2 | 8 | 1 | 5 | |||

Increment L until it finds an item larger than the pivot. | ||||||||||||

Decrement R. | ||||||||||||

Swap items L and R through swap var T. | ||||||||||||

4 | 7 | 4 | 7 | 3 | 6 | 2 | 8 | 1 | 5 | |||

4 | 7 | 4 | 1 | 3 | 6 | 2 | 8 | 1 | 5 | |||

4 | 7 | 4 | 1 | 3 | 6 | 2 | 8 | 7 | 5 | |||

Increment L until it finds an item larger than the pivot. | ||||||||||||

Decrement R. | ||||||||||||

Swap items L and R through swap var T. | ||||||||||||

4 | 6 | 4 | 1 | 3 | 6 | 2 | 8 | 7 | 5 | |||

4 | 6 | 4 | 1 | 3 | 8 | 2 | 8 | 7 | 5 | |||

4 | 6 | 4 | 1 | 3 | 8 | 2 | 6 | 7 | 5 | |||

Increment L until it finds an item larger than the pivot. | ||||||||||||

Decrement R. | ||||||||||||

Swap items L and R through swap var T. | ||||||||||||

4 | 8 | 4 | 1 | 3 | 8 | 2 | 6 | 7 | 5 | |||

4 | 8 | 4 | 1 | 3 | 2 | 2 | 6 | 7 | 5 | |||

4 | 8 | 4 | 1 | 3 | 2 | 8 | 6 | 7 | 5 | |||

Increment L — now L is not less than R, so... | ||||||||||||

...decrement L... | ||||||||||||

...and swap item L and the first item through swap var T. | ||||||||||||

4 | 2 | 4 | 1 | 3 | 2 | 8 | 6 | 7 | 5 | |||

4 | 2 | 4 | 1 | 3 | 4 | 8 | 6 | 7 | 5 | |||

4 | 2 | 2 | 1 | 3 | 4 | 8 | 6 | 7 | 5 | Done. | ||

piv |
T |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |

Of the data values 3, 8, and 7 (none of which need to move) only 3 is left alone, and 8 is moved twice. The swap variable is used five times (or five and a half if you count copying out the pivot value, which is part of the single swap my code uses).

Here’s a modified version that never fails — i.e. it never runs into its MAX_LEVELS limit:

// quickSort // // This public-domain C implementation by Darel Rex Finley. // // * This function assumes it is called with valid parameters. // // * Example calls: // quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4 // quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7 void quickSort(int *arr, int elements) { #define MAX_LEVELS 300 int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ; beg[0]=0; end[0]=elements; while (i>=0) { L=beg[i]; R=end[i]-1; if (L<R) { piv=arr[L]; while (L<R) { while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; } arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; if (end[i]-beg[i]>end[i-1]-beg[i-1]) { swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap; swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; }} else { i--; }}} |

This might be slightly slower than the first one, but it will never fail because it always performs the smaller partition first. Hence, the only way it could run into the limit is if the to-be-sorted array was at least 2

(Note: Someone reminded me that a typically 64-bit index variable can index only 2

Bugs? Performance tests? Questions? I’d love to hear about it — please shoot me an e-mail.

Back to Tutorials.