and here is the source code that you will need :

public class ArraySorter

{

private static >

int getIndexOfSmallest(T[] a, int first, int last)

{

T min = a[first];

int indexOfMin = first;

for (int index = first + 1; index

{

if (a[index].compareTo(min)

{

min = a[index];

indexOfMin = index;

} // end if

// Assertion: min is the smallest of a[first] through a[index].

} // end for

return indexOfMin;

} // end getIndexOfSmallest

// INSERTION SORT

public static >

void insertionSort(T[] a, int n)

{

insertionSort(a, 0, n - 1);

} // end insertionSort

public static >

void insertionSort(T[] a, int first, int last)

{

for (int unsorted = first + 1; unsorted

{ // Assertion: a[first]

T firstUnsorted = a[unsorted];

insertInOrder(firstUnsorted, a, first, unsorted - 1);

} // end for

} // end insertionSort

private static >

void insertInOrder(T anEntry, T[] a, int begin, int end)

{

int index = end;

while ((index >= begin) && (anEntry.compareTo(a[index])

{

a[index + 1] = a[index]; // Make room

index--;

} // end for

// Assertion: a[index + 1] is available

a[index + 1] = anEntry; // Insert

} // end insertInOrder

// SHELL SORT

public static >

void shellSort(T[] a, int n)

{

shellSort(a, 0, n - 1);

} // end shellSort

/** Sorts equally spaced elements of an array into

ascending order.

@param a An array of Comparable objects.

@param first An integer >= 0 that is the index of the first

array element to consider.

@param last An integer >= first and

index of the last array element to consider.

@param space The difference between the indices of the

elements to sort. */

public static >

void shellSort(T[] a, int first, int last)

{

int n = last - first + 1; // Number of array entries

int space = n / 2;

while (space > 0)

{

for (int begin = first; begin

{

incrementalInsertionSort(a, begin, last, space);

} // end for

space = space / 2;

} // end while

} // end shellSort

// BETTER SHELL SORT

/** Avoids even spacing */

public static >

void betterShellSort(T[] a, int n)

{

betterShellSort(a, 0, n - 1);

} // end betterShellSort

// Exercise 14, Chapter 8

public static >

void betterShellSort(T[] a, int first, int last)

{

int n = last - first + 1; // Number of array elements

for (int space = n / 2; space > 0; space = space / 2)

{

if (space % 2 == 0) // If space is even, add 1

space++;

for (int begin = first; begin

incrementalInsertionSort(a, begin, last, space);

} // end for

} // end betterShellSort

private static >

void incrementalInsertionSort(T[] a, int first, int last, int space)

{

int unsorted, index;

for (unsorted = first + space; unsorted

unsorted = unsorted + space)

{

T nextToInsert = a[unsorted];

index = unsorted - space;

while ((index >= first) && (nextToInsert.compareTo(a[index])

{

a[index + space] = a[index];

index = index - space;

} // end while

a[index + space] = nextToInsert;

} // end for

} // end incrementalInsertionSort

private static void swap(Object[] a, int i, int j)

{

Object temp = a[i];

a[i] = a[j];

a[j] = temp;

} // end swap

} // end ArraySorter

2. Implement the insertion sort and the Shell sort so that they count the number of comparisons made during a sort. Use your implementations to compare the two sorts on arrays of random Integer objects of various sizes. Also, compare the Shell sort as implemented in Segment 8.23 with a revised Shell sort that adds 1 to space any time it is even. For what array size does the difference in the number of comparisons become significant? Is the size consistent with the size predicted by the algorithm's Big Oh? 2. Implement the insertion sort and the Shell sort so that they count the number of comparisons made during a sort. Use your implementations to compare the two sorts on arrays of random Integer objects of various sizes. Also, compare the Shell sort as implemented in Segment 8.23 with a revised Shell sort that adds 1 to space any time it is even. For what array size does the difference in the number of comparisons become significant? Is the size consistent with the size predicted by the algorithm's Big Oh