Java Reference
In-Depth Information
else if
(begin < end)
{
a[end
+
1] = a[end]
insertInOrder(anEntry, a, begin, end
-
1)
}
else
// begin == end and anEntry < a[end]
{
a[end
+
1] = a[end]
a[end] = anEntry
}
Look back at the iterative algorithm
insertionSort
given in Segment 8.11. For an array of
n
entries,
first
is 0 and
last
is
n
-
1. The
for
loop then executes
n
-
1 times, and so the method
insertInOrder
is invoked
n
-
1 times. Thus, within
insertInOrder
,
begin
is 0 and
end
ranges
from 0 to
n
-
2. The loop within
insertInOrder
executes at most
end
-
begin
+
1 times each time
the method is invoked. Thus, this loop executes at most a total of
1
+
2
+
. . .
+
(
n
-
1)
times. This sum is
n
(
n
-
1)
/
2, so the insertion sort is O(
n
2
). The recursive insertion sort performs
the same operations as the iterative insertion sort, so it is also O(
n
2
).
This analysis provides a worst-case scenario. In the best case, the loop in
insertInOrder
would exit immediately. Such is the case if the array is sorted already. In the best case, then, inser-
tion sort is O(
n
). In general, the more sorted an array is, the less work
insertInOrder
needs to do.
This fact and its relatively simple implementation make the insertion sort popular for applications
in which the array does not change much. For example, some customer databases add only a small
percentage of new customers each day.
The next chapter will use the insertion sort when the array size is small.
Note:
The time efficiency of insertion sort
Insertion sort is at best O(
n
) and at worst O(
n
2
). The closer an array is to sorted order, the less
work an insertion sort does.
Usually you will sort arrays, but sometimes you might need to sort a chain of linked nodes. When
you do, the insertion sort is one that is easy to understand.
Figure 8-9 shows a chain whose nodes contain integers that are sorted into ascending order. To
begin to see how we can construct an insertion sort for a chain, imagine that we want to insert a
node into this chain so that the integers in the nodes remain in sorted order.
FIGURE 8-9
A chain of integers sorted into ascending order
2
5
10
3
8
firstNode
