Below is the pseudocode for Quicksort and Partition. 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
Questions:
A) 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?
B) 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)?