Answer Happy

Consider the pseudocode description of a recursive implementation of the quick sort algorithm below.

ALGORITHM:partition(data[0:n-1], from, to)
{arranges (partitions) the elements of the subarray data[from:to] such that
all the entries from data[from:p] are less than or equal to the pivot and the
entries of data[p+1:to] are greater than or equal to the pivot. The pivot is
data[from], the first entry of the subarray, prior to generating the partition}
Input: data - an array of n items
from - the first index of the subarray of data that is to be partitioned
to - the last index of the subarray of data that is to be partitioned
Output: the index p such that data[from:p] <= data[p+1:to]
i := from -1
j := to + 1
pivot := data[from]
while i < j do
i := i + 1
while data < pivot do
i : = i + 1
end
j := j - 1
while data[j] > pivot do
j : = j - 1
end
if i < j then
swap(data, data[j])
end
end
return j
END

ALGORITHM:quickSort(data[0:n-1], from, to)
{sorts the subarray data[from:to] using the quick sort algorithm}
Input: data - an array of n items
from - the first index of the subarray of data that is to be sorted
to - the last index of the subarray of data that is to be sorted
if from < to then
p := partition(data,from,to)
quickSort(data, from, p)
quickSort(data,p+1, to)
end
END
A. Give the partitions generated by the algorithm during the first three calls to the partition subroutine by giving the contents of the array after the subarray was partitioned, from (the first index of the subarray that was partitioned, to (the last index of the subarray that was partitioned, and the return value (the last index of the left partition). The initial call is quickSort([5, 13, 9, 11, 9, 14, 9], 0, 6).
After 1st call to partition: from= ______ to= _______ partition index = _______
Contents of data after the First Call to partition (7 blanks)
_____ _____ _____ _____ _____ _____ _____
After 2nd call to partition: from= ______ to= _______ partition index = _______
Contents of data after the Second Call to partition (7 blanks)
_____ _____ _____ _____ _____ _____ _____
After 3rd call to partition: from= ______ to= _______ partition index = _______
Contents of data after the Third Call to partition (7 blanks)
_____ _____ _____ _____ _____ _____ _____
B. Give the contents of the array that is used as the argument to quickSort, from (the first index of its subarray that is to be sorted), and to (the last index of its subarray that is to be sorted) during the indicated call.
4th Call to quickSort: from= ______ to= _______
Contents of data Used as the Argument to quicksort (7 blanks)
_____ _____ _____ _____ _____ _____ _____
8th Call to quickSort: from= ______ to= _______
Contents of data Used as the Argument to quicksort (7 blanks)
_____ _____ _____ _____ _____ _____ _____