Java Reference
In-Depth Information
•
Compare
33
with
15
; it is bigger, so insert
33
in location
1
. This gives the following:
33
by comparing it with the numbers to its left, starting
with the nearest one. As long as
key
is less than
num[k]
, for some
k
, we move
num[k]
to
position
num[k + 1]
and move on to consider
num[k-1]
, providing it exists. If
key
is greater
than or equal to
num[k]
for some
k
, then
key
is inserted in position
k+1
. Here,
33
is greater
than
num[0]
and so is inserted into
num[1]
.
•
We can express the logic of placing
6
th
pass
num[6]
, that is,
52
. This involves placing
52
so that the first seven (all) numbers are
sorted. This is done as follows:
•
Process
52
in
key
, leaving location
6
free.
•
Store
52
with
79
; it is smaller, so move
79
to location
6
, leaving location
5
free.
•
Compare
52
with
65
; it is smaller, so move
65
to location
5
, leaving location
4
free.
•
Compare
52
with
57
; it is smaller, so move
57
to location
4
, leaving location
3
free.
•
Compare
52
with
48
; it is bigger; so insert
52
in location
3
. This gives the following:
•
Compare
The array is now completely sorted.
The following is an outline of how to sort the first
n
elements of an array,
num
, using insertion sort:
for h = 1 to n - 1 do
insert num[h] among num[0] to num[h-1] so that num[0] to num[h] are sorted
endfor
Using this outline, we write the function
insertionSort
using the parameter
list
.
public static void insertionSort(int list[], int n) {
//sort list[0] to list[n-1] in ascending order
for (int h = 1; h < n; h++) {
int key = list[h];
int k = h - 1; //start comparing with previous item
while (k >= 0 && key < list[k]) {
list[k + 1] = list[k];
--k;
}
list[k + 1] = key;
} //end for
} //end insertionSort
The
while
statement is at the heart of the sort. It states that as long as we are within the array (
k >= 0
) and
the current number (
key
) is less than the one in the array (
key < list[k]
), we move
list[k]
to the right
(
list[k+1] = list[k]
) and move on to the next number on the left (
--k
).
Search WWH ::
Custom Search