public void insertionSort(E[] data, Comparator<? super E> compare);
public void bubbleSort(E[] data, Comparator<? super E> compare);
public void selectionSort(E[] data, Comparator<? super E> compare);
Each method should implement the named simple sort algorithm on the array data. Use the Comparator<E> to determine the order of the items in the array. Sort the arrays in ascending order. The ‘smallest’ element should be in position 0, ‘largest’ in array.length - 1.
The methods should keep track of the number of comparisons, number of swaps and the amount of time it took to sort the array. To record the time taken, your code should call System.nanoTime at the beginning of each of the methods and save the value as the start time. It should then call System.nanoTime again at the end, and print the difference between the two times. The difference may be zero if your system clock does not update the time quickly enough, but otherwise should accurately report how many nanoseconds (billionths of a second) it took to execute your code. When the sort methods complete they should report the number of comparison, swaps, and the execution time in nanoseconds.
Be sure to thoroughly test your code. Turn in your test code along with your Class.
Write up a runtime analysis of each of the sorting methods, giving the big-O of each, and explaining how you got your results. Send your analysis to the TA together with your code. This part counts for 25% of the grade on this assignment. Even if your code doesn’t work, you should do this part to the best of your ability.
The assignment is due on Friday at 11:59pm. You may turn it in early. If you haven’t completed the assignment by 11:58, turn in what you have. Getting partial credit is much better then no credit.