Resending to try to clarify the prose and fix a typo in the final tree.
You don't need to start from scratch. Insertion Sort "knows"
what comparisons to make, and the logic in the program
(quit the inner loop as soon as you find something smaller)
embodies exactly " if a<b, and b<c, then a<c".
The actions that insertion sort takes on the array,
swaping adjacent members in the inner loop,
track exactly what you will need to have in hand
when you reach a leaf. Let's try this for 3 elements.
Start with [a, b, c].
// inner loop for (j = 1; j > 0; j--)
is a < b?
There are two possible outcomes: it is or it isn't.
Unlike Robert Frost, you get to take both paths.
Alternate universe 1: a < b We don't need to change anything,
so we have [a, b, c]
Alternate universe 2: a < b is false, so we swap a, b,
and get [b, a, c].
We now have the following picture
if (a < b)
/ \
[a,b,c] [b,a,c]
Now we insert the third element, c.
I am only going to take the right branch: the
left is similar.
Starting from [b, a, c] (end of right branch)
// inner loop for (j = 2; j > 0; j--)
is a < c?
Door number 1: yes! Nothing needs to change: we have
[b, a, c] and we break out of loop.
Alternate universe 3: no, a is not < c.
Swap a and c, and consider [b,c,a]
is b < c? // Note that I am comparing a[0] with a[1]
Door Number 2: yes! Nothing needs to change.
We break out of loop.
Door Number 3: No, I need to swap to get [c, b, a]
and I break out of loop because j == 0.
Putting these together, I get
if (a < b)
/ \
[a,b,c] [b,a,c]
if (a < c)
/ \
[b, a, c] [b, c, a]
if (b < c)
/ \
[b, c, a] [c, b, a]
The arrays are only printed at the end, but they are
carried along at every step. They embody what you
know so far about the array, and help you decide
which question to ask next.
This isn't a full tree: I haven't done the right subtree
yet. However, I think the left subtree is more instructive
as the items are no so well ordered.
- jeff parker
