Java Reference
In-Depth Information
While selecting the median in this way is guaranteed to eliminate a fraction of
the elements (leaving at most d(7n5)=10e elements left), we still need to be sure
that our recursion yields a linear-time algorithm. We model the algorithm by the
following recurrence.
T(n) T(dn=5e) + T(d(7n 5)=10e) + 6dn=5e + n 1:
The T(dn=5e) term comes from computing the median of the medians-of-fives,
the 6dn=5e term comes from the cost to calculate the median-of-fives (exactly six
comparisons for each group of five element), and the T(d(7n5)=10e) term comes
from the recursive call of the remaining (up to) 70% of the elements that might be
left.
We will prove that this recurrence is linear by assuming that it is true for some
constant r, and then show that T(n) rn for all n greater than some bound.
T(n) T(d
n
5
e) + T(d
7n 5
10
e) + 6d
n
5
e + n 1
r(
n
5
+ 1) + r(
7n 5
10
+ 1) + 6(
n
5
+ 1) + n 1
(
r
5
7r
10
11
5
3r
2
+
+
)n +
+ 5
9r + 22
10
3r + 10
2
n +
:
This is true for r 23 and n 380. This provides a base case that allows us to
use induction to prove that 8n 380; T(n) 23n:
In reality, this algorithm is not practical because its constant factor costs are so
high. So much work is being done to guarantee linear time performance that it is
more efficient on average to rely on chance to select the pivot, perhaps by picking
it at random or picking the middle value out of the current subarray.
15.7
Optimal Sorting
We conclude this section with an effort to find the sorting algorithm with the ab-
solute fewest possible comparisons. It might well be that the result will not be
practical for a general-purpose sorting algorithm. But recall our analogy earlier to
sports tournaments. In sports, a “comparison” between two teams or individuals
means doing a competition between the two. This is fairly expensive (at least com-
pared to some minor book keeping in a computer), and it might be worth trading a
fair amount of book keeping to cut down on the number of games that need to be
played. What if we want to figure out how to hold a tournament that will give us
the exact ordering for all teams in the fewest number of total games? Of course,
we are assuming that the results of each game will be “accurate” in that we assume