Java Reference
In-Depth Information
FIGURE 8-8
Inserting the first unsorted entry into the sorted portion of the
array. (a) The entry is greater than or equal to the last sorted
entry; (b) the entry is smaller than the last sorted entry
(a)
9
9
8, so it belongs after 8
4
6
8
Sorted
4
6
8
9
Sorted
(b)
3
3
8, so...
2
5
8
Sorted
shift 8, and ...
2
5
8
Sorted
3
insert 3 into the rest of the sorted portion
2
5
8
Sorted
8.14
The algorithm
insertInOrder
: final draft.
This algorithm is not quite right. The
else
clause will
work only if we have more than one entry in the remaining portion of the array—that is, if
begin
<
end
.
If
begin
and
end
were equal, for example, the recursive call would be equivalent to
insertInOrder(anEntry, a, begin, begin - 1);
which is incorrect.
Will
end
ever equal
begin
, if they were not equal initially? Yes. When
anEntry
is less than all
entries
a[begin]
, . . . ,
a[end]
, each recursive call decreases
end
by 1 until eventually
end
equals
begin
. What should we do when this happens? Since the sorted portion consists of one entry
a[end]
, we will move
a[end]
to the next higher position and place
anEntry
in
a[end]
.
The following revised algorithm reflects these changes:
Algorithm
insertInOrder(anEntry, a, begin, end)
//
Inserts
anEntry
into the sorted array entries
a[begin]
through
a[end]
.
//
Revised draft.
if
(anEntry >= a[end])
a[end
+
1] = anEntry
