Below is the pseudocode for Quicksort and Partition that we talked about in class. As usual with recursive functions on arrays, we see the array indices s and e as arguments. Quicksort(A, s, e) sorts the part of the array between s and e inclusively. The initial call (that is, to sort the entire array) is Quicksort(A, 0, n − 1).
QuickSort(A, s, e)

if s < e

p = Partition (A, s, e) // Partition the array and return the position of pivot after the partition

QuickSort(A, s, p-1) // Sort left side

QuickSort (A, p+1, e) // Sort right side

end if

Partition(A, s, e)

pivot = A[s], i = s + 1, j = e; // Let the leftmost element be the pivot

while i<=j // Rearrange elements

while i < e & A[i] < pivot,

i = i + 1

end while

while j > s & A[j] >= pivot,

j = j - 1

end while

if i >= j

break

end if

swap A[i] nd A[j]

end while

swap A[s] nd A[j]

return j; // Return the index of pivot after the partition

a)Let A = {11, 7, 6, 48, 30, 12, 75}, and assume we call Quicksort(A, 0, 6). Show what happens during the first invocation of Partition. What is the value of p returned, and what are the two recursive calls made?
Note: Credit will not be given only for answers - show all your work:

(5 points) steps you took to get your answer.

(2 points) your answer.

b)How do you modify Partition(A, s, e) so that it chooses the pivot as the median of three elements randomly selected from the array?
(3 points) pseudocode to change Partition.

c)How do you modify Partition(A, s, e) so that it always chooses the pivot uniformly at random from the array (instead of shuffling the array initially)?
(2 points) pseudocode to change Partition.