Using the PARTITION and QUICKSORT routines bellow, what value of q does each PARTITION return for the following cases? Justify your answer for each case.

(1) when all elements in A[p..r] are distinct and sorted in ascending order?

(2) when all elements in A[p..r] are distinct and sorted in descending order?

QuickSort(A, p, r)

if p < r

q = Partition(A, p, r)

QuickSort(A, p, q 1)

QuickSort(A, q + 1, r)

Partition(A, p, r)

x = A[r] # x is the pivot.

i = p 1

for j = p to r 1

if A[j] x

i = i + 1

exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1