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.
19.7.1 Insertion Sort Implementation
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.)
 
Search WWH ::




Custom Search