Given the following code:

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];

i = p -1;

for(j = p to r-1){

if(A[j] <= x){

i++;

exchange A[i] with A[j]

}

}

Exchange A[i+1] with A[r];

return i+1;

}

a. Run Partition(A, 1, 10) on the array A = {6, 3, 10, 7, 4, 9, 2, 8, 1, 5}.

b. What value of q does Partition return when all elements in the array A[pr] has the same value? What would be a running time of QuickSort in this case?

c. What is the best case running time of QuickSort?

d. What is the worst case running time of QuickSort? How can we improve the worst case running time of QuickSort?