> > My problem, however,
>> is that I don't understand how we create these
>> "decisions". I mean, how do I write a program that
> > understands "well, if a<b, and b<c, then a<c and
>> therefore I write a,b,c"??? How does the program know,
>> for instance, to put a,b at the first node, b,c and
>> a,c at the second level nodes, then either a leaf or
> > a<c at the third level on the left, etc etc etc???
Not to detract from Hans response, but let me say a word about this.
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,
tracks 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].
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 doesn't need to change anything,
so we have [a, b, c]
Alternate universe 2: a < b is false, so we sway a, b,
and get [b, a, c].
We now have the following picture
if (a < b)
/ \
[a,b,c] [b,a,c]
Now we proceed down each of these in turn.
I am only going to take the right branch: the
left is equivalent.
Starting from [b, a, c] (end of right branch)
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: is different. Swap, 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)
/ \
[c, b, a] [b, c, 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.
This isn't a full tree: I haven't done the right subtree
yet. However, I think the left subtree is more instructive.
- jeff parker
