Java Reference
In-Depth Information
figure 8.4
A closer look at the
action of insertion sort
(the dark shading
indicates the sorted
area; the light shading
is where the new
element was placed)
0
1
2
3
4
5
Array Position
Initial State
8
5
After
a[0..1]
is sorted
5
8
9
After
a[0..2]
is sorted
5
8
9
2
After
a[0..3]
is sorted
2
5
8
9
6
After
a[0..4]
is sorted
2
5
6
8
9
3
After
a[0..5]
is sorted
2
3
5
6
8
9
temporary variable and sliding all the elements that are larger than it one
position to the right. Then we can copy the temporary variable into the
former position of the leftmost relocated element (indicated by lighter shad-
ing on the following line). We keep a counter
j
, which is the position to
which the temporary variable should be written back. Every time an element
is slid,
j
decreases by 1. Lines 9-14 implement this process.
Because of the nested loops, each of which can take
N
iterations, the
insertion sort algorithm is
O
(
N
2
). Furthermore, this bound is achievable
because input in reverse order really does take quadratic time. A precise cal-
culation shows that the tests at line 12 in Figure 8.2 can be executed at most
P +
1 times for each value of
P
. Summing over all
P
gives a total time of
The
insertion sort
is
quadratic in the
worst and average
cases. It is fast if
the input has
already been
sorted.
N
1
-
N
234
…
∑
(
P
1
+
)
=
∑
i
=
+++ +
N
=
Θ
()
N
2
P
=
1
i
=
2
However, if the input is presorted, the running time is
O
(
N
) because the test
at the top of the inner
for
loop always fails immediately. Indeed, if the input is
almost sorted (we define
almost sorted
more rigorously shortly), the insertion
sort will run quickly. Thus the running time depends not only on the amount of
input, but also on the specific ordering of the input. Because of this wide varia-
tion, analyzing the average-case behavior of this algorithm is worthwhile. The
average case turns out to be
θ
(
N
2
) for the insertion sort as well as a variety of
other simple sorting algorithms.
An
inversion
is a pair of elements that are out of order in an array. In other
words, it is any ordered pair (
i, j
) having the property that
i
<
j
but . For
example, the sequence {8, 5, 9, 2, 6, 3} has 10 inversions that correspond to
the pairs (8, 5), (8, 2), (8, 6), (8, 3), (5, 2), (5, 3), (9, 2), (9, 6), (9, 3), and
(6, 3). Note that the number of inversions equals the total number of times
that line 13 in Figure 8.2 is executed. This condition is always true because
An
inversion
measures
unsortedness.
A
i
A
j
>
Search WWH ::
Custom Search