The quicksort algorithm sorts an array by first selecting a pivot entry
and partitioning the array about that element.
The partition operation rearranges the entries, placing the pivot entry
in its proper sort position.
After the partition, entries before (in index order) the pivot entry are
less than the pivot entry.
Entries after the pivot entry are greater than or equal to the pivot
entry.
This is illustrated in the following diagram, where the index
geq points to the pivot entry.
| lo | geq | hi | |
| < | = | >= |
Then the quicksort algorithm recursively sorts the entries before the pivot entry and the entries after the pivot entry.
After checking if there is more than one element (if not then just return), a pivot element is selected and swapped with the end entry. This is done to keep the pivot entry in a known place. It will later be swapped into its proper place.
Two variables geq and unk are set equal to
lo, the lowest index in the array segment.
This indicates that the "<" and ">=" segments of the array are
currently empty.
A variable end is set equal to hi - 1, where
hi is the index just beyond the end of the segment.
This results in the following picture.
The partition loop only works with the portion outlined in blue.
| unk | ||
| geq | ||
| lo | end | hi |
| ? | = |
Here ? indicates unknown entries - entries that have not yet
been examined.
The two preceding pictures can be generalized into a single picture that covers both.
| lo | geq | unk | end | hi |
| < | >= | ? | = |
Here, < indicates entries that are less than the pivot
and >= indicates entries that are greater than or equal
to the pivot.
Since this picture covers both the starting picture, the end result, and intermediate steps, it can be used as a loop invariant.
Each iteration of the loop checks the entry at index unk.
If it is less than piv then the entry is swapped with the
entry at geq and both geq and unk
are advanced.
Otherwise unk is advanced.
In either case, the loop invariant is preserved.
When finally unk == end we have the following picture.
| unk | |||
| lo | geq | end | hi |
| < | >= | = |
Now the entry at index geq is swapped with the pivot at
index end.
This results in the following picture.
| lo | geq | hi | |
| < | = | >= |
After achieving this picture, the array can be completely sorted by
recursively sorting the < and >= regions.