Java Reference
In-Depth Information
The numbers have been sorted in ascending order.
The method described illustrates the idea behind
insertion sort
. The numbers in the array will be processed one
at a time, from left to right. This is equivalent to picking up the numbers from the table one at a time. Since the first
number, by itself, is sorted, we will process the numbers in the array starting from the second.
When we come to process
num[h]
, we can assume that
num[0]
to
num[h-1]
are sorted. We insert
num[h]
among
num[0]
to
num[h-1]
so that
num[0]
to
num[h]
are sorted. We then go on to process
num[h+1]
. When we do so, our
assumption that
num[0]
to
num[h]
are sorted will be true.
Sorting
num
in ascending order using insertion sort proceeds as follows:
1
st
pass
•
Process
num[1]
, that is,
48
. This involves placing
48
so that the first two numbers are sorted;
num[0]
and
num[1]
now contain the following:
The rest of the array remains unchanged.
2
nd
pass
•
Process
num[2]
, that is,
79
. This involves placing
79
so that the first three numbers are sorted;
num[0]
to
num[2]
now contain the following:
The rest of the array remains unchanged.
3
rd
pass
num[3]
, that is,
65
. This involves placing
65
so that the first four numbers are sorted;
num[0]
to
num[3]
now contain the following:
•
Process
The rest of the array remains unchanged.
4
th
pass
num[4]
, that is,
15
. This involves placing
15
so that the first five numbers are sorted.
To simplify the explanation, think of 15 as being taken out and stored in a simple variable
(
key
, say) leaving a “hole” in
num[4]
. We can picture this as follows:
•
Process
Search WWH ::
Custom Search