Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 4 and 5 Hints for Quicksort
Due Friday, March 3, and Friday, March 10, 2000.

A quicksort algorithm is any
sorting algorithm whose fundamental action is to split an unsorted list of
items into two (or perhaps more) smaller unsorted lists, where the criteria
used for the splitting is whether an item is greater or smaller than a
specific pivot item (or items, if there are more than two
sublists), then sort the sublists and put them back together to form a
final sorted list. There are many variations.
The Basic Idea.
If the list is short, use some simple sorting algorithm such as the
array implementation of selection sort, and you're done. Otherwise:
-
Pick a pivot item from the list.
-
Move the pivot aside, and rearrange the list so that all items less than
the pivot are on the "left" and all items greater than the pivot are
on the "right."
-
Recursively sort the left and the right.
-
Restore the original list in sorted form by appending the pivot to the
left list, then appending the right list.
The Equal Split Problem.
The algorithm performs badly unless the left and right sublists are
frequently close to equal size. The definitions of "frequently" and
"close" are rather generous.
The ideal pivot is the median item.
The problem with that choice is that it's hard to find. The amount
of time needed to find the median is so great that you might as
well have used a slower algorithm such as heapsort.
The leftmost item, rightmost item, middle item, and the median of those
three, are various choices of pivot that can be used. All result
in quadratic performance of the algorithm in the worst case.
The Las Vegas
method is to pick an item at random from the list and make it the
pivot. This gives good expected time complexity.
Duplicate Items.
If the list contains many duplicates, the algorithm could take quadratic
time, regardless of the choice of pivot. The simple reason is that if
most of the items in the list are equal to the pivot, the split function
could put all of them into the same sublist.
There are at least two ways to overcome this problem. One way is to
split the list into 3 parts, those less than the pivot, those equal to
the pivot (the "middle" sublist) and those greater than the pivot.
Then, only the left and right need to be sorted.
Another technique is to rewrite the code for the split function
so as to permit an item equal to the pivot to be placed into either the
left or the right, making sure it is done in a "fair" manner.
