Analysis of Algorithms : An Active Learning Approach

90 SORTING ALGORITHMS

Splitting the List

There are at least two versions of the PivotList function. The first is easy to

program and understand and is presented in this section. The other is more

complicated to write but is faster than this version. The second version will be

considered in the exercises.

The function PivotList will pick the first element of the list as its pivot

element and will set the pivot point as the first location of the list. It then

moves through the list comparing this pivot element to the rest of the ele-

ments. Whenever it finds an element that is smaller than the pivot element, it

will increment the pivot point and then swap this element into the new pivot

point location. After some of the elements are compared to the pivot inside the

loop, we will have four parts to the list. The first part is the pivot element in

the first location. The second part is from location first + 1 through the pivot

point and will be all of the elements we have looked at that are smaller than the

pivot element. The third part is from the location after the pivot point through

the loop index and will be all of the elements we have looked at that are larger

than the pivot element. The rest of the list will be values we have not yet

examined. This is shown in Fig. 3.4.

The algorithm for PivotList is as follows:

PivotList( list, first, last )

list the elements to work with

first the index of the first element

last the index of the last element

PivotValue = list[ first ]

PivotPoint = first

for index = first + 1 to last do

if list[ index ] < PivotValue then

pivot < pivot ≥ pivot unknown

Pivot

Point

First Index Last

■FIGURE 3.4

Relationship

between the

indices and

element values in

PivotList