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: 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.