1D Arrays and Sorting:

You are given the source code for four sorting algorithms, namely, insertion sort, selection sort, quick sort, and merge sort. Each algorithm is implemented in a single java source file, e.g., quick sort is in file QuickSort.java.

Step 1: Modify each sorting algorithm so that it keeps track of the number of comparisons it performs and the number of exchanges (swaps) it performs during a single sorting operation. Keep track of these numbers using two long integer counters; one to keep track of the number of comparisons and another to keep track of the number of swaps.

Step 2: Write a driver program (i.e., a main program) that instantiates a selection sort, quick sort, merge sort, and insertion sort objects and then instructs each object to sort an array of 50,000 random integer elements, then 100,000 elements, then 200,000 elements, then 300,000 elements, and finally 400,000 elements. Your program should record on the output console the number of exchanges and comparisons for each algorithm and each data set that was sorted. Your program should also keep track of how much time each sorting algorithm needed to sort each array. Hence, for each algorithm you should record the time elapsed for each of the five sorting processes [Hint: use Javas java.lang.System.currentTimeMillis() method, which returns a long integer that represents the current time in milliseconds. You will need to call this method twice, once just before the sorting process, and once right after the sorting process. The difference will be the time elapsed in milliseconds].

Here are the insertion sort, selection sort, quick sort, and merge sort files: https://www.dropbox.com/sh/fsyldmisjqr7sb5/AAAM31Oi8XNN2d4CESHDn-q5a?dl=0