University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
A Quicksort Example
Revised October 18, 2005
![](../../bluhorsa.gif)
We start with an array of letters, HELPMESEETHIS, and sort it
using quicksort. We will follow the following rules:
-
The pivot item is always take to be the first item of the subarray
being sorted.
-
At each iteration of the main loop of Partition:
-
If possible, we increment "lo" by one.
-
If possible, we decrement "hi" by one. (We might both increment
"lo" and decrement "hi" in one iteration.)
-
If neither of those is possible, we swap and then increment "lo"
and decrement "hi."
-
When "lo" and "hi" meet, we exchange the pivot item with the rightmost
item in the left portion. (If the left portion is empty, we do nothing.)
-
If there are two or more subarrays that need to be sorted, we sort the
smaller one first. If they are of equal size, we sort the leftmost one
first.
-
In the illustrated file, we show the array at
each step.
-
Items known to be in their final positions are colored
black.
-
Items in the subarray that is
currently being sorted that have not be inspected are colored orange.
-
The pivot item is colored blue.
-
Items in the left portion of the subarray currently being sorted
are colored red.
-
Items in the right portion of the subarray currently being sorted
are colored green.
-
Items in any subarray that has not been sorted and is not currently
being sorted are colored brown.
Updated Tuesday, October 18, 6:33 AM. The previous file had only one
error, namely that I failed to follow the rule that when you recursively
sort the two subarrays after partititioning, you sort the smaller one
first. If you follow this rule, the depth of the recursion is
Theta(log n), while if you don't, it's O(n), although the algorithm is still
correct.
Here is another example.
Here is another example.
![](../../bluhorsa.gif)