An alternative for the PivotList algorithm would be to have two indices

into the list. The first moves up from the bottom and the other moves down

from the top. The main loop of the algorithm will advance the lower index

until a value greater than the Pivotvalue is found, and the upper index is

moved until a value less than the PivotValue is found. Then these two are

swapped. This process repeats until the two indices cross. These inner loops

are very fast because the overhead of checking for the end of the list is elim$-$

inated, but the problem is that they will do an extra swap when the indices

pass each other. So$,$ the algorithm does one extra swap to correct this. The

full algorithm is

Pivothist $($ 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 $]$

lower $=$ first

upper $=1$ ast $+1$

do

do upper $=$ upper $-1$ until list $[$upper$]$ PivotValue

do lower $=$ lower $+1$ until list $[$lower$]$ Pivotvalue

Swap $(1$ist $[$ upper $],1$ist $[$ lower $])$

until lower $$ upper

$//$ undo the extra exchange

Swap $($ list $[$ upper $],$ list$[$ lower $])$

$//$ move pivot point into correct place

Swap$($ list$[$ first $],$ list $[$ upper $])$

return upper

c$.$ What operation is done significantly less frequently for this version of

PivotList?