Java Reference

In-Depth Information

of an array is already sorted. (When the algorithm starts, we set
k
to
0
.) We

enlarge the initial sequence by inserting the next array element,
a[k + 1]
, at the

proper location. When we reach the end of the array, the sorting process is

complete.

For example, suppose we start with the array

Of course, the initial sequence of length 1 is already sorted. We now add
a[1]
,

which has the value 9. The element needs to be inserted before the element 11. The

result is

Next, we add
a [2]
, which has the value 16. As it happens, the element does not

have to be moved.

We repeat the process, inserting
a[3]
or 5 at the very beginning of the initial

sequence.

Finally,
a[4]
or 7 is inserted in its correct position, and the sorting is completed.

The following class implements the insertion sort algorithm:

public class InsertionSorter

{

/**

Constructs an insertion sorter.

@param anArray
the array to sort

*/

public InsertionSorter(int[] anArray)

{

a = anArray;

}

637