Description
1. We can improve the running time of quicksort in practice by taking advantage of the fast running time of
insertion sort when its input is ”nearly” sorted. Upon calling quicksort on a subarray with fewer than k
elements, let it simply return without sorting the subarray.
After the top-level call to quicksort returns,
run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm
runs in O(nk + n lg( n
k
)) expected time. How should we pick k, both in theory and in practice?
2. Quicksort with equal element values. The analysis of the expected running time of the randomized
quicksort assumes that all element values are distinct. In this problem, we examine what happens when
they are not.
(a) Suppose that all element values are equal. What would be randomized quicksort’s running time in
this case?
(b) The PARTITION procedure returns an index q such that each element of A[p, . . . , q −1] is less than
or equal to A[q] and each element of A[q + 1, . . . , r] is greater than A[q]. Modify the PARTITION
procedure to produce a procedure PARTITION’(A, p, r), which permutes the elements of A[p, . . . , r]
and returns two indices q and t, where p ≤ q ≤ t ≤ r, such that
i. all elements of A[q, . . . , t] are equal,
ii. each element of A[p, . . . , q − 1] is less than A[q], and
iii. each element of A[t + 1, . . . , r] is greater than A[q].
Like PARTITION, your PARTITION’ procedure should take Θ(r − p) time.
(c) Modify the RANDOMIZED-PARTITION procedure to call PARTITION’, and name the new procedure RANDOMIZED-PARTITION’. Then modify the QUICKSORT procedure to produce a procedure QUICKSORT’(A, p, r) that calls RANDOMIZED-PARTITION’ and recurses only on partitions
of elements not known to be equal to each other.
(d) Using QUICKSORT’, how would you adjust the analysis of randomized quicksort to avoid the
assumption that all elements are distinct?
3. Similar to the example shown in slides, illustrate the operation of COUNTING-SORT on
A = [5, 9, 7, 2, 3, 6, 9, 5, 2, 1]
4. Prove the lower bound of ⌈
3n
2
⌉−2 comparisons in the worst case to find both the maximum and minimum
of n numbers. (Hint: consider how many numbers are potentially either the maximum or miminum, and
investigate how a comparison affects these counts.)
5. Largest i numebrs in sorted order. Given a set of n numbers, we wish to find the i largest in
sorted order using a comparison-based algorithm. Find the algorithm that implements each of the
following methods with the best asymptotic worst-case running time, and analyze the running times of
the algorithms in terms of n and i.
(a) Sort the numbers, and list the i largest.
(b) Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.
(c) Use an order-statistic algorithm to find the ith largest number, partition around that number, and
sort the i largest numbers.
