Java Reference
In-Depth Information
...
i−1
...
n−i
Figure15.4
The poset that represents the minimum information necessary to
determine the ith element in a list. We need to know which element has i 1
values less and ni values more, but we do not need to know the relationships
among the elements with values less or greater than the ith element.
U : U
(i 2; j + 1; k + 1; l)
L : U
(i 1; j + 1; k;
l)
W : U (i 1; j;
k + 1; l)
W : W (i;
j 1; k;
l + 1)
L : L
(i;
j;
k 1; l + 1)
Only the last two transition types increase the number of middles, so there
must be n2 of these. The number of untested elements must go to 0, and the first
transition is the most efficient way to do this. Thus, dn=2e of these are required.
Our conclusion is that the minimum possible number of transitions (comparisons)
is n + dn=2e 2. Thus, our algorithm is optimal.
15.6
Finding the
i
th Best Element
We now tackle the problem of finding the ith best element in a list. As observed
earlier, one solution is to sort the list and simply look in the ith position. However,
this process provides considerably more information than we need to solve the
problem. The minimum amount of information that we actually need to know can
be visualized as shown in Figure 15.4. That is, all we need to know is the i 1
items less than our desired value, and the ni items greater. We do not care about
the relative order within the upper and lower groups. So can we find the required
information faster than by first sorting? Looking at the lower bound, can we tighten
that beyond the trivial lower bound of n comparisons? We will focus on the specific
question of finding the median element (i.e., the element with rank n=2), because
the resulting algorithm can easily be modified to find the ith largest value for any i.
Looking at the Quicksort algorithm might give us some insight into solving the
median problem. Recall that Quicksort works by selecting a pivot value, partition-
ing the array into those elements less than the pivot and those greater than the pivot,
and moving the pivot to its proper location in the array. If the pivot is in position i,
then we are done. If not, we can solve the subproblem recursively by only consid-
ering one of the sublists. That is, if the pivot ends up in position k > i, then we
