Simultaneous minimum and maximum
A simple algorithm to find the minimum and maximum is to find each one independently.
There will be n − 1 comparisons for the minimum and n − 1 comparisons
for the maximum, for a total of 2n −2 comparisons. This will result in (n) time.
In fact, at most 3 n/2 comparisons are needed to find both the minimum and
maximum:
• Maintain the minimum and maximum of elements seen so far.
• Don.t compare each element to the minimum and maximum separately.
• Process elements in pairs.
• Compare the elements of a pair to each other.
• Then compare the larger element to the maximum so far, and compare the
smaller element to the minimum so far.
This leads to only 3 comparisons for every 2 elements.
Setting up the initial values for the min and max depends on whether n is odd or
even.
• If n is even, compare the first two elements and assign the larger to max and the
smaller to min. Then process the rest of the elements in pairs.
• If n is odd, set both min and max to the first element. Then process the rest of
the elements in pairs.
Selection in expected linear time
Selection of the i th smallest element of the array A can be done in (n) time.
The function RANDOMIZED-SELECT uses RANDOMIZED-PARTITION from the
quicksort algorithm in Chapter 7. RANDOMIZED-SELECT differs from quicksort
because it recurses on one side of the partition only.
RANDOMIZED-SELECT(A, p, r, i )
if p = r
then return A[p]
q ←RANDOMIZED-PARTITION(A, p, r )
k ← q − p + 1
if i = k pivot value is the answer
then return A[q]
elseif i < k
then return RANDOMIZED-SELECT(A, p, q − 1, i )
else return RANDOMIZED-SELECT(A, q + 1, r, i − k)
Selection in worst-case linear time
Idea: Guarantee a good split when the array is partitioned.
• Will use the deterministic procedure PARTITION, but with a small modiÞcation.
Instead of assuming that the last element of the subarray is the pivot, the
modiÞed PARTITION procedure is told which element to use as the pivot.
SELECT works on an array of n > 1 elements. It executes the following steps:
1. Divide the n elements into groups of 5. Get n/5 groups: n/5
groups with
exactly 5 elements and, if 5 does not divide n, one group with the remaining
n mod 5 elements.
2. Find the median of each of the n/5 groups:
• Run insertion sort on each group. Takes O(1) time per group since each
group has ≤ 5 elements.
• Then just pick the median from each group, in O(1) time.
3. Find the median x of the n/5 medians by a recursive call to SELECT. (If
n/5 is even, then follow our convention and Þnd the lower median.)
4. Using the modiÞed version of PARTITION that takes the pivot element as input,
partition the input array around x. Let x be the kth element of the array after
partitioning, so that there are k −1 elements on the low side of the partition and
n − k elements on the high side.
5. Now there are three possibilities:
• If i = k, just return x.
• If i < k, return the i th smallest element on the low side of the partition by
making a recursive call to SELECT.
• If i > k, return the (i −k)th smallest element on the high side of the partition
by making a recursive call to SELECT.
Show that the second smallest of n elements can be found with n + ⌈lg n⌉ - 2 comparisons in
the worst case. (Hint: Also find the smallest element.)
In the search for the smallest number, the second smallest number must have come
out smallest in every comparison made with it until it was eventually compared
with the smallest. So the second smallest is among the elements that were compared
with the smallest during the tournament. To find it, conduct another tournament
(as above) to find the smallest of these numbers. At most lg n (the height
of the tree of comparisons) elements were compared with the smallest, so finding
the smallest of these takes lg n − 1 comparisons in the worst case.
The total number of comparisons made in the two tournaments was
n − 1 + lg n − 1 = n + lg n − 2
in the worst case.
Exercises 9.3-1
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm
work in linear time if they are divided into groups of 7? Argue that SELECT does not run in
linear time if groups of 3 are used.
Exercises 9.3-3
Show how quicksort can be made to run in O(n lg n) time in the worst case.
A modiÞcation to quicksort that allows it to run in O(n lg n) time in the worst case
uses the deterministic PARTITION algorithm that was modiÞed to take an element
to partition around as an input parameter.
SELECT takes an array A, the bounds p and r of the subarray in A, and the rank i
of an order statistic, and in time linear in the size of the subarray A[p . . r ] it returns
the i th smallest element in A[p . . r ].
BEST-CASE-QUICKSORT(A, p, r )
if p < r
then i ← (r − p + 1)/2
x ←SELECT(A, p, r, i )
q ←PARTITION(x)
BEST-CASE-QUICKSORT(A, p, q − 1)
BEST-CASE-QUICKSORT(A, q + 1, r )
Because BEST-CASE-QUICKSORT always recurses on subarrays that are at most
half the size of the original array, the recurrence for the worst-case running time is
T (n) ≤ 2T (n/2) + O(n) = O(n lg n).
Exercises 9.3-5
Suppose that you have a "black-box" worst-case linear-time median subroutine. Give a
simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.
Given MEDIAN, here is a linear-time algorithm SELECT for Þnding the i th smallest
element in A[p . . r ]. This algorithm uses the deterministic PARTITION algorithm
that was modiÞed to take an element to partition around as an input parameter.
SELECT
(A, p, r, i )
if p = r
then return A[p]
x ←MEDIAN(A, p, r )
q ←PARTITION(x)
k ← q − p + 1
if i = k
then return A[q]
elseif i < k
then return SELECT
(A, p, q − 1, i )
else return SELECT
(A, q + 1, r, i − k)
Because x is the median of A[p . . r ], each of the subarrays A[p . . q − 1] and
A[q + 1 . . r ] has at most half the number of elements of A[p . . r ]. The recurrence
for the worst-case running time of SELECT is T (n) ≤ T (n/2) + O(n) = O(n).
Exercises 9.3-8
Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order.
Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.
TWO-ARRAY-MEDIAN(X, Y )
n ← length[X] // n also equals length[Y ]
median ← FIND-MEDIAN(X, Y, n, 1, n)
if median = NOT-FOUND
then median ← FIND-MEDIAN(Y, X, n, 1, n)
return median
FIND-MEDIAN(A, B, n, low, high)
if low > high
then return NOT-FOUND
else k ← (low+high)/2
if k = n and A[n] ≤ B[1]
then return A[n]
elseif k < n and B[n − k] ≤ A[k] ≤ B[n − k + 1]
then return A[k]
elseif A[k] > B[n − k + 1]
then return FIND-MEDIAN(A, B, n, low, k − 1)
else return FIND-MEDIAN(A, B, n, k + 1, high)
Exercises 9.3-9
Professor Olay is consulting for an oil company, which is planning a large pipeline running
east to west through an oil field of n wells. From each well, a spur pipeline is to be connected
directly to the main pipeline along a shortest path (either north or south), as shown in Figure
9.2. Given x- and y-coordinates of the wells, how should the professor pick the optimal
location of the main pipeline (the one that minimizes the total length of the spurs)? Show that
the optimal location can be determined in linear time
In order to Þnd the optimal placement for Professor Olay’s pipeline, we need only
Þnd the median(s) of the y-coordinates of his oil wells, as the following proof
explains.
Claim
The optimal y-coordinate for Professor Olay’s east-west oil pipeline is as follows:
• If n is even, then on either the oil well whose y-coordinate is the lower median
or the one whose y-coordinate is the upper median, or anywhere between them.
• If n is odd, then on the oil well whose y-coordinate is the median.
Problems 9-1: Largest i numbers in sorted order
Given a set of n numbers, we wish to find the i largest in sorted order using a comparisonbased
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.
Total worst-case running time:(n + i lg n).
==> Limit heap size to i
c. Use an order-statistic algorithm to find the ith largest number, partition around that
number, and sort the i largest numbers.
c. Use the SELECT algorithm of Section 9.3 to Þnd the i th largest number in (n)
time. Partition around that number in (n) time. Sort the i largest numbers in
(i lg i ) worst-case time (with merge sort or heapsort).
Total worst-case running time: (n + i lg i ).
Problems 9-2: Weighted median
