Analysis of Algorithms : An Active Learning Approach

3.7 QUICKSORT 89

3.7 Quicksort

Quicksort is another recursive sorting algorithm. It picks an element from the

list and uses it to divide the list into two parts. The first part has all of the ele-

ments that are smaller than the one chosen, and the second part has all of the

elements that are larger. We saw this process when we looked at the selection

problem in Section 2.3. The Quicksort algorithm is different because it is

then applied recursively to both parts. This is an efficient sort on average, but

its worst case is the same as insertion and bubble sort.

Quicksort chooses an element of the list, called the pivot element, and then

rearranges the list so that all of the elements smaller than the pivot are moved

before it and all of the elements larger than the pivot are moved after it. The

elements in each of the two parts of the list are not put in order. If the pivot

element winds up in location i, all we know is that the elements in locations 1

through i
 1 are smaller than the pivot element and those in locations i + 1

through N are larger than the pivot. Quicksort is then called recursively for

these two parts. If Quicksort is called with a list containing one element, it

does nothing because a one-element list is sorted.

Because the determination of the pivot point and the movement of the ele-

ments into the proper section do all of the work, the main Quicksort algo-

rithm just needs to keep track of the bounds of these two sections. Further,

because splitting the list into two parts is where the keys are moved around, all

of the sorting work is done on the way down in the recursive process. Recall

that this is the opposite of merge sort, which does its work on the way back up

in the recursive process.

The algorithm for quicksort is

Quicksort( list, first, last )
list the elements to be put into order
first the index of the first element in the part of list to sort
last the index of the last element in the part of list to sort

if first < last then
pivot = PivotList( list, first, last )
Quicksort( list, first, pivot-1 )
Quicksort( list, pivot+1, last )
end if