Java Reference
In-Depth Information
I=1
2
17
20
42
13
28
14
23
15
3
4
5
6
7
42
20
17
13
28
14
23
15
20
42
17
13
28
14
23
15
13
17
20
42
28
14
23
13
17
20
28
42
14
23
13
14
17
20
28
42
23
13
14
17
20
23
28
42
13
14
15
17
20
23
28
42
15
15
15
15
Figure7.1
An illustration of Insertion Sort. Each column shows the array after
the iteration with the indicated value of
i
in the outer
for
loop. Values above
the line in each column have been sorted. Arrows indicate the upward motions of
records through the array.
following is a Java implementation. The input is an array of n records stored in
array
A
.
static<EextendsComparable<?superE>>
voidSort(E[]A){
for(inti=1;i<A.length;i++)//Inserti'threcord
for(intj=i;(j>0)&&(A[j].compareTo(A[j-1])<0);j--)
DSutil.swap(A,j,j-1);
}
Consider the case where
inssort
is processing the ith record, which has key
value X. The record is moved upward in the array as long as X is less than the
key value immediately above it. As soon as a key value less than or equal to X is
encountered,
inssort
is done with that record because all records above it in the
array must have smaller keys. Figure 7.1 illustrates how Insertion Sort works.
The body of
inssort
is made up of two nested
for
loops. The outer
for
loop is executed n 1 times. The inner
for
loop is harder to analyze because
the number of times it executes depends on how many keys in positions 1 to i 1
have a value less than that of the key in position i. In the worst case, each record
must make its way to the top of the array. This would occur if the keys are initially
arranged from highest to lowest, in the reverse of sorted order. In this case, the
number of comparisons will be one the first time through the
for
loop, two the
second time, and so on. Thus, the total number of comparisons will be
n
X
i n
2
=2 = (n
2
):
i=2
In contrast, consider the best-case cost. This occurs when the keys begin in
sorted order from lowest to highest. In this case, every pass through the inner
for
loop will fail immediately, and no values will be moved. The total number
