Java Reference
In-Depth Information
XYZ
XYZ
XZY
YXZ
YZX
ZXY
ZYX
YES
NO
A[1]<A[0]?
(Y<X?)
XYZ
XYZ
XZY
ZXY
YXZ
YXZ
YZX
ZYX
YES
NO
YES
NO
A[2]<A[1]?
A[2]<A[1]?
(Z<X?)
(Z<Y?)
YZX
YZX
ZYX
YXZ
XZY
XYZ
XZY
ZXY
YES
NO
YES
NO
A[1]<A[0]?
A[1]<A[0]?
(Z<Y?)
(Z<X?)
ZYX
YZX
ZXY
XZY
Figure7.21
Decision tree for Insertion Sort when processing three values la-
beled X, Y, and Z, initially stored at positions 0, 1, and 2, respectively, in input
array A.
compared and the first is less than the second, then this is modeled as a left branch
in the decision tree. In the case where the first value is greater than the second, the
algorithm takes the right branch.
Figure 7.21 shows the decision tree that models Insertion Sort on three input
values. The first input value is labeled X, the second Y, and the third Z. They are
initially stored in positions 0, 1, and 2, respectively, of input array
A
. Consider the
possible outputs. Initially, we know nothing about the final positions of the three
values in the sorted output array. The correct output could be any permutation of
the input values. For three values, there are n! = 6 permutations. Thus, the root
node of the decision tree lists all six permutations that might be the eventual result
of the algorithm.
When n = 3, the first comparison made by Insertion Sort is between the sec-
ond item in the input array (Y) and the first item in the array (X). There are two
possibilities: Either the value of Y is less than that of X, or the value of Y is not
less than that of X. This decision is modeled by the first branch in the tree. If Y is
less than X, then the left branch should be taken and Y must appear before X in the
final output. Only three of the original six permutations have this property, so the
left child of the root lists the three permutations where Y appears before X: YXZ,
YZX, and ZYX. Likewise, if Y were not less than X, then the right branch would
be taken, and only the three permutations in which Y appears after X are possible
outcomes: XYZ, XZY, and ZXY. These are listed in the right child of the root.
Let us assume for the moment that Y is less than X and so the left branch is
taken.
In this case, Insertion Sort swaps the two values.
At this point the array
