Quicksort Algorithm to Complete given Trace-Multiple Choice Question

Question

Consider the following quicksort algorithm

Quicksort(first, last)

{IF (first < last) // There is more than one item

splitVal = data[first];

splitPoint = Split(splitVal);

left = first + 1;

right = last;

WHILE (left <= right)

{Increment left until data[left] > splitVal OR left > right;

Decrement right until data[right] < splitVal OR left > right;

IF(left < right)

Swap data[left] and data[right]

}

splitPoint = right;

Swap data[first] and data[splitPoint];

Quicksort(first, splitPoint - 1);

Quicksort(splitPoint + 1, last)

}

Each recursive call to the Quicksort function acts on a portion of the array to be sorted. Illustrate how the algorithm works on the data by completing the trace below. For each call of Quicksort give the index values for first and last as well as the value (splitVal) used as a pivot value. Also show the state of the array being sorted after the evaluation of all the Quicksort functions applied to the array.

You may not need to complete all the tables below.