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
23.1
Insertion sort repeatedly inserts a new element into a sorted sublist.
[0][1][2][3][4][5]
2
[6]
Step 1: Save 4 to a temporary variable
currentElement
currentElement:
list
594
4
[0][1][2][3][4][5]
[6]
list
2
5
9
Step 2: Move
list[2]
to
list[3]
[0][1][2][3][4][5]
[6]
list
2
5
9
Step 3: Move
list[1]
to
list[2]
[0][1][2][3][4][5]
2
[6]
list
Step 4: Assign
currentElement
to
list[1]
459
F
IGURE
23.2
A new element is inserted into a sorted sublist.
The algorithm can be expanded and implemented as in Listing 23.1.
L
ISTING
23.1
InsertionSort.java
1
public class
InsertionSort {
2
/** The method for sorting the numbers */
3
public static void
insertionSort(
int
[] 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
int
currentElement = list[i];
8
int
k;
9
for
(k = i -
1
; k >=
0
&& list[k] > currentElement; k--) {
10 list[k +
1
] = list[k];
shift
Search WWH ::
Custom Search