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
Search WWH ::




Custom Search