Java Reference
In-Depth Information
not only that the outcome of A playing B would always be the same (at least over
the time period of the tournament), but that transitivity in the results also holds. In
practice these are unrealistic assumptions, but such assumptions are implicitly part
of many tournament organizations. Like most tournament organizers, we can sim-
ply accept these assumptions and come up with an algorithm for playing the games
that gives us some rank ordering based on the results we obtain.
Recall Insertion Sort, where we put element i into a sorted sublist of the first i
1 elements. What if we modify the standard Insertion Sort algorithm to use binary
search to locate where the ith element goes in the sorted sublist? This algorithm
is called binary insert sort. As a general-purpose sorting algorithm, this is not
practical because we then have to (on average) move about i=2 elements to make
room for the newly inserted element in the sorted sublist. But if we count only
comparisons, binary insert sort is pretty good. And we can use some ideas from
binary insert sort to get closer to an algorithm that uses the absolute minimum
number of comparisons needed to sort.
Consider what happens when we run binary insert sort on five elements. How
many comparisons do we need to do? We can insert the second element with one
comparison, the third with two comparisons, and the fourth with 2 comparisons.
When we insert the fifth element into the sorted list of four elements, we need to
do three comparisons in the worst case. Notice exactly what happens when we
attempt to do this insertion. We compare the fifth element against the second. If the
fifth is bigger, we have to compare it against the third, and if it is bigger we have
to compare it against the fourth. In general, when is binary search most efficient?
When we have 2
i
1 elements in the list. It is least efficient when we have 2
i
elements in the list. So, we can do a bit better if we arrange our insertions to avoid
inserting an element into a list of size 2
i
if possible.
Figure 15.6 illustrates a different organization for the comparisons that we
might do. First we compare the first and second element, and the third and fourth
elements. The two winners are then compared, yielding a binomial tree. We can
view this as a (sorted) chain of three elements, with element A hanging off from the
root. If we then insert element B into the sorted chain of three elements, we will
end up with one of the two posets shown on the right side of Figure 15.6, at a cost of
2 comparisons. We can then merge A into the chain, for a cost of two comparisons
(because we already know that it is smaller then either one or two elements, we are
actually merging it into a list of two or three elements). Thus, the total number of
comparisons needed to sort the five elements is at most seven instead of eight.
If we have ten elements to sort, we can first make five pairs of elements (using
five compares) and then sort the five winners using the algorithm just described
(using seven more compares). Now all we need to do is to deal with the original
losers. We can generalize this process for any number of elements as:
• Pair up all the nodes with b
n
2
c comparisons.
