Randomized quicksort is a popular divide-and-conquer sorting algorithm. Below is the pseudo-code for this algorithm:
function quicksort(A)
if (length(A) <= some constant S) then
return slowsort(A)
else
k = random integer drawn uniformly from integers in [0, length(A) - 1]
(left, pivot, right) = partition(A, k)
return concatenate(quicksort(left), pivot, quicksort(right))
end if
end function
function partition(A, k)
pivot = A[k]
// We are assuming that the list contains no duplicates, so no other element is equal to the pivot
left = elements in A that are smaller than pivot
right = elements in A that are larger than pivot
return (left, pivot, right)
end function
Assume that partition(A) takes a * length(A) time units and slowsort(A) takes b * length(A)^2 time units. Further assume that the total running time is simply equal to the sum of the running times of all calls to partition() and slowsort(). As seen in the pseudo-code, quicksort does not call itself recursively on lists of length S or less, but instead calls slowsort().
Consider using the randomized quicksort algorithm to sort a list that is some permutation of elements {x | 1 <= x < listSize}. Hence, the list is of length listSize, only contains integers between 1 and listSize, inclusive, and contains no duplicates. You are given the constants a, b and S, and asked to compute the expected total running time of randomized quicksort on a list of size listSize that obeys the constraints given above.
|