Question

1. What will be the resulting list after the following algorithm has been applied to the list:

{21, 17, 23, 3, 42, 9, 30} where first = 1 and last = 7. [10 pts]

     Int Partition (list, first, last)

PivotValue = list[ first ]

PivotPoint = first

for index = first+1 to last do

   if list[ index ] < PivotValue then

        PivotPoint = PivotPoint + 1

        Swap( list[ PivotPoint ], list[ index ] )

   end if

end for

// move pivot value into correct place

Swap( list[ first ], list[ PivotPoint ] )

return PivotPoint

b) Explain what this algorithm is doing? [5 pts]

c) What is the time complexity of this algorithm? [5 pts]

Answer 1