Write a Java Program that measures the running time of different sorting routines. Implement the following sorting algorithms and measure times for 1,000, 10,000, 100,000 and 1,000,000 elements: All sort, Insertion Sort, Enhanced Insertion Sort, List Insertion Sort, MergeSort, ShellSort, QuickSort, and Improved QuickSort. Use seconds as a unit of time. Show the result in table as shown:

Please keep as much of the Test Class in tact as possible, including class names and method names. *Note that you would need more classes to implement, for example, you need LinkedList class for Link Insertion Sort. Please provide the code in text as well as a screenshot of the output.

Use the following Test Class:

////////////////////////////////

public class HW4 {

public static void main(String[] args) {

int arySize = 1000;

long startTime, timeTaken;

while (arySize

ArraySort arySort = new ArraySort(arySize);

// For Insertion Sort

arySort.initArray();

startTime = System.currentTimeMillis();

arySort.insertionSort();

timeTaken = System.currentTimeMillis() - startTime;

System.out.println(arySort);

System.out.println("Time taken for Insertion Sort: " +

timeTaken + " msec");

// For Enhanced Insertion Sort

arySort.initArray();

startTime = System.currentTimeMillis();

arySort.enhancedInsertionSort();

...

arySort.listInsertionSort();

...

arySort.mergeSort();

...

arySort.shellSort();

...

arySort.quickSort();

...

arySort.improvedQuickSort();

...

arySize *= 10;

} // end of while

}

}

class ArraySort

{

private long[] ary; // ref to array a, unsorted

private int size; // array size

public ArraySort(int max) // constructor

{

ary = new long[max]; // create the array

size = max;

}

public String toString() // displays array: first 10 and last 10

{

return "SortedArray";

}

public void initArray()

{

Random rand = new Random(0);

for (int i = 0; i

ary[i] = rand.nextInt(size * 20);

}

public void insertionSort() { ... }

public void enhancedInsertionSort() { ... }

...

}

Insert. Enhanced Sort List Insert. MergeSort ShelSort QuickSort Improved QuickSort Insert. Sort Sort 1,000 10,000 100,000 1,000,000