Add a method insertionSort to the class ArraySorter, as given in Listing 7.10, that performs an insertion sort of an array. To simplify this project, our insertion sort algorithm will use an additional array. It copies elements from the original given array to this other array, inserting each element into its correct position in the second array. This will usually require moving a number of elements in the array receiving the new elements. The algorithm in pseudocode is as follows:

Insertion sort algorithm to sort an array a

for (index = 0; index Insert the value of a[index] into its correct position in the array
temp, so that all the elements copied into the array temp so far are sorted.

Copy all the elements from temp back to a.
The array temp is partially filled and is a local variable in the method sort.

Listing 7.10

/**
Class for sorting an array of base type int from smallest to largest.
*/
public class ArraySorter
{
/**
Precondition: Every element in anArray has a value.
Action: Sorts the array into ascending order.
*/
public static void selectionSort(int[] anArray)
{
for (int index = 0; index < anArray.length − 1; index++)
{ // Place the correct value in anArray[index]
int indexOfNextSmallest = getIndexOfSmallest(index,
anArray);
interchange(index, indexOfNextSmallest, anArray);
//Assertion:anArray[0] <= anArray[1] <=…<= anArray[index]
//and these are the smallest of the original array elements.
//The remaining positions contain the rest of the original
//array elements.
}
}
/**
Returns the index of the smallest value in the portion of the
array that begins at the element whose index is startIndex and
ends at the last element.
*/
private static int getIndexOfSmallest(int startIndex, int[] a)
{
int min = a[startIndex];
int indexOfMin = startIndex;
for (int index = startIndex + 1; index < a.length; index++)
{
if (a[index] < min)
{
min = a[index];
indexOfMin = index;
//min is smallest of a[startIndex] through a[index]
}
}
return indexOfMin;
}
/**
Precondition: i and j are valid indices for the array a.
Postcondition: Values of a[i] and a[j] have been interchanged.
*/
private static void interchange(int i, int j, int[] a)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp; //original value of a[i]
}
}