Java Reference
In-Depth Information
48
23
59
42
11
17
89
93
12
88
91
12
64
57
34
90
Figure17.1
An illustration of PAIRING. The two lists of numbers are paired up
so that the least values from each list make a pair, the next smallest values from
each list make a pair, and so on.
Figure 17.1 illustrates PAIRING. One way to solve PAIRING is to use an exist-
ing sorting program to sort each of the two sequences, and then pair off items based
on their position in sorted order. Technically we say that in this solution, PAIRING
is reduced to SORTING, because SORTING is used to solve PAIRING.
Notice that reduction is a three-step process. The first step is to convert an
instance of PAIRING into two instances of SORTING. The conversion step in this
example is not very interesting; it simply takes each sequence and assigns it to an
array to be passed to SORTING. The second step is to sort the two arrays (i.e., apply
SORTING to each array). The third step is to convert the output of SORTING to
the output for PAIRING. This is done by pairing the first elements in the sorted
arrays, the second elements, and so on.
A reduction of PAIRING to SORTING helps to establish an upper bound on the
cost of PAIRING. In terms of asymptotic notation, assuming that we can find one
method to convert the inputs to PAIRING into inputs to SORTING “fast enough,”
and a second method to convert the result of SORTING back to the correct result
for PAIRING “fast enough,” then the asymptotic cost of PAIRING cannot be more
than the cost of SORTING. In this case, there is little work to be done to convert
from PAIRING to SORTING, or to convert the answer from SORTING back to the
answer for PAIRING, so the dominant cost of this solution is performing the sort
operation. Thus, an upper bound for PAIRING is in O(n log n).
It is important to note that the pairing problem does not require that elements
of the two sequences be sorted. This is merely one possible way to solve the prob-
lem. PAIRING only requires that the elements of the sequences be paired correctly.
Perhaps there is another way to do it? Certainly if we use sorting to solve PAIR-
ING, the algorithms will require (n log n) time.
But, another approach might
conceivably be faster.
