Java Reference
In-Depth Information
Step 1: Initially, the sorted sublist contains the
first element in the list. Insert 9 into the sublist.
2
9
5
4
8
1
6
Step 2: The sorted sublist is {2, 9}. Insert 5 into
the sublist.
2
9
5
4
8
1
6
Step 3: The sorted sublist is {2, 5, 9}. Insert 4
into the sublist.
2
5
9
4
8
1
6
Step 4: The sorted sublist is {2, 4, 5, 9}. Insert 8
into the sublist.
2
4
5
9
8
1
6
Step 5: The sorted sublist is {2, 4, 5, 8, 9}. Insert
1 into the sublist.
2
4
5
8
9
1
6
Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9}.
Insert 6 into the sublist.
1
2
4
5
8
9
6
Step 7: The entire list is now sorted.
1
2
4
5
6
8
9
F
IGURE
6.13
Insertion sort repeatedly inserts a new element into a sorted sublist.
[0][1][2][3][4][5][6]
2594
list
Step 1: Save 4 to a temporary variable
currentElement
[0][1][2][3][4][5][6]
25
list
Step 2: Move
list[2]
to
list[3]
9
[0][1][2][3][4][5][6]
2
list
5
9
Step 3: Move
list[1]
to
list[2]
[0][1][2][3][4][5][6]
2459
list
Step 4: Assign
currentElement
to
list[1]
F
IGURE
6.14
A new element is inserted into a sorted sublist.
The algorithm can be expanded and implemented as in Listing 6.9.
L
ISTING
6.9
InsertionSort.java
1
public class
InsertionSort {
2
/** The method for sorting the numbers */
3
public static void
insertionSort(
double
[] list) {
4
for
(
int
i =
1
; i < list.length; i++) {
5
/** Insert list[i] into a sorted sublist list[0..i-1] so that
6
list[0..i] is sorted. */
7
double
currentElement = list[i];
8
int
k;
9
10 list[k +
1
] = list[k];
11 }
12
13
for
(k = i -
1
; k >=
0
&& list[k] > currentElement; kââ) {
shift
// Insert the current element into list[k + 1]
