The quicksort algorithm was invented by C.A.R. Hoare in 1962. I learned about it from "The C Programming Language, Second Edition" by Brian W. Kernighan and Dennis M. Ritchie (page 87). I found the K&R code a bit hard to follow; I believe I've come upon a better way of explaining the algorithm, using a few figures of speech.
The point of any sort routine is to take an array of objects and arrange the objects in some kind of sequence. We might, for example, want to take this collection of numbers:
06 34 69 33 75 64 04 74 25 95 15 58 78 36 51 73 13 27
and put them into numerical order, with the
smallest number first, like this:
04 06 13 15 25 27 33 34 36 51 58 64 69 73 74 75 78 95
The general approach of the quick sort is to select an element from the middle (or from close to the middle) of an array and then put all other elements which are less than or equal to the selected element to its left and all elements which are greater than the selected element to its right. The selected element is called the "pivot element" because the other elements, figuratively speaking, turn around it. This crude "sorting" around the pivot element yields two sub-arrays: a left one and a right one. If, for example, we start with the original array above and use "25" as the pivot element, our first sorting yields:
[ 04 06 15 13 ] 25 [ 64 34 74 69 95 33 58 78 36 51 73 75 27 ]The next step is for quicksort to call itself to have the left and right sub-arrays sorted. Of course, a "sub array" with zero elements or only one element is already in proper order and does not need to be sorted. The interesting part of the quick sort is how it comes up with the sub arrays. I will illustrate.
From our original array, take out the element in (or close to) the middle of the array for a pivot element. This, figuratively speaking, leaves a hole in the array:
06 34 69 33 75 64 04 74 __ 95 15 58 78 36 51 73 13 27
p.e. = 25
Now "move the hole" to the first position in the
array by moving the current occupant of that
position into the current hole's position:
__ 34 69 33 75 64 04 74 06 95 15 58 78 36 51 73 13 27
p.e. = 25
Now we get to work. We start with the first
element to the right of the hole. If it is
greater than the pivot element, we do nothing.
If it is less than or equal to the pivot
element, then
we want to put the element in the hole and then
re-establish the hole immediately to the right of
the moved element.
The first element of our sample array that needs
to be moved is "04":
+-----------------+
| |
V |
04 34 69 33 75 64 __ 74 06 95 15 58 78 36 51 73 13 27
+--------------+
| |
| V
04 __ 69 33 75 64 34 74 06 95 15 58 78 36 51 73 13 27
p.e. = 25
After we similarly process "06" we will have:
04 06 __ 33 75 64 34 74 69 95 15 58 78 36 51 73 13 27
p.e. = 25
At the end of the process, we have:
04 06 15 13 __ 64 34 74 69 95 33 58 78 36 51 73 75 27
p.e. = 25
As you can see, all elements to the left
of the hole are less than the pivot element; all
elements to the right of the hole are greater than
the pivot element.
To finish up, we sort the left sub-array then the
right sub-array, then we stuff the pivot element
back into the hole and we are done.
I believe writing one's own quicksort is a fine exercise. The URL for my version, commented using the above figures of speech, is: http://m3peeps.org/quicksort.c
Copyright © 2004
You may make paper or electronic copies of this essay
for your own enjoyment and edification.
If you wish to link to this article, try copying and pasting:
<a href="http://m3peeps.org/qs.htm">The Quicksort Explained</a>