Java Reference
In-Depth Information
stores YXZ. Thus, in Figure 7.21 the left child of the root shows YXZ above the
line. Next, the third value in the array is compared against the second (i.e., Z is
compared with X). Again, there are two possibilities. If Z is less than X, then these
items should be swapped (the left branch). If Z is not less than X, then Insertion
Sort is complete (the right branch).
Note that the right branch reaches a leaf node, and that this leaf node contains
only one permutation: YXZ. This means that only permutation YXZ can be the
outcome based on the results of the decisions taken to reach this node. In other
words, Insertion Sort has “found” the single permutation of the original input that
yields a sorted list. Likewise, if the second decision resulted in taking the left
branch, a third comparison, regardless of the outcome, yields nodes in the decision
tree with only single permutations. Again, Insertion Sort has “found” the correct
permutation that yields a sorted list.
Any sorting algorithm based on comparisons can be modeled by a decision tree
in this way, regardless of the size of the input. Thus, all sorting algorithms can
be viewed as algorithms to “find” the correct permutation of the input that yields
a sorted list. Each algorithm based on comparisons can be viewed as proceeding
by making branches in the tree based on the results of key comparisons, and each
algorithm can terminate once a node with a single permutation has been reached.
How is the worst-case cost of an algorithm expressed by the decision tree? The
decision tree shows the decisions made by an algorithm for all possible inputs of a
given size. Each path through the tree from the root to a leaf is one possible series
of decisions taken by the algorithm. The depth of the deepest node represents the
longest series of decisions required by the algorithm to reach an answer.
There are many comparison-based sorting algorithms, and each will be mod-
eled by a different decision tree. Some decision trees might be well-balanced, oth-
ers might be unbalanced. Some trees will have more nodes than others (those with
more nodes might be making “unnecessary” comparisons). In fact, a poor sorting
algorithm might have an arbitrarily large number of nodes in its decision tree, with
leaves of arbitrary depth. There is no limit to how slow the “worst” possible sort-
ing algorithm could be. However, we are interested here in knowing what the best
sorting algorithm could have as its minimum cost in the worst case. In other words,
we would like to know what is the smallest depth possible for the deepest node in
the tree for any sorting algorithm.
The smallest depth of the deepest node will depend on the number of nodes
in the tree. Clearly we would like to “push up” the nodes in the tree, but there is
limited room at the top. A tree of height 1 can only store one node (the root); the
tree of height 2 can store three nodes; the tree of height 3 can store seven nodes,
and so on.
Here are some important facts worth remembering:
• A binary tree of height n can store at most 2
n
1 nodes.
