Java Reference
In-Depth Information
Using this algorithm, at the
i
th iteration, the first
i
elements of the original array are sorted,
but they may not be in their final locations—smaller values may be located later in the array.
Class
InsertionSortTest
(Fig. 19.5) contains:
•
static
method
insertionSort
to sort
int
s using the insertion sort algorithm
•
static
method
printPass
to display the array contents after each pass, and
•
main
to test method
insertionSort
.
Method
main
(lines 53-68) is identical to
main
in Fig. 19.4 except that line 64 calls method
insertionSort
.
1
// Fig. 19.5: InsertionSortTest.java
2
// Sorting an array with insertion sort.
3
import
java.security.SecureRandom;
4
import
java.util.Arrays;
5
6
public class
InsertionSortTest
7
{
8
// sort array using insertion sort
9
public static void
insertionSort(
int
[] data)
10
{
11
// loop over data.length - 1 elements
12
for
(
int
next =
1
; next < data.length; next++)
13
{
14
int
insert = data[next];
// value to insert
int
moveItem = next;
// location to place element
15
16
17
// search for place to put current element
while
(moveItem >
0
&& data[moveItem -
1
] > insert)
{
// shift element right one slot
data[moveItem] = data[moveItem -
1
];
moveItem--;
}
18
19
20
21
22
23
24
25
data[moveItem] = insert;
// place inserted element
26
printPass(data, next, moveItem);
// output pass of algorithm
27
}
28
}
29
30
// print a pass of the algorithm
31
public static void
printPass(
int
[] data,
int
pass,
int
index)
32
{
33
System.out.printf(
"after pass %2d: "
, pass);
34
35
// output elements till swapped item
36
for
(
int
i =
0
; i < index; i++)
37
System.out.printf(
"%d "
, data[i]);
Fig. 19.5
|
Sorting an array with insertion sort. (Part 1 of 3.)