Problem
Modify the Insertion Sort provided by the author, to accept an array of 8,000 integers as input***. This array must be generated using the uniform distribution provided by the author with the StdRandom class. Run the program by modifying DoublingTest.java from section 1.4 and measure your insertion sort times. Add also the StopWatch class to measure the elapse time from every run of the insertion sort. Run the test for 100 times and output the elapse time in each run. You will need the performance measurements generated by your program later on.
Create a static method called ShuffleSome that accepts the array as input and shuffle N/200 elements from the array. You must choose the elements to be exchange in a random fashion. (You can use the exch(a, i, j) call by choosing i and j randomly). Then, use the StopWatch class to measure only the elapse time from every run of the Insertion Sort using this "partially sorted" array. Therefore, You should sort the array, then shuffle it, then measure only the elapse time in the final insertion sort.
Create another run but now run insertion sort 2 times. One with the uniformly distributed unsorted array created by StdRandom class and a second time using the sorted array as input. Then, use the StopWatch class to measure only the elapse time from every run of the Insertion Sort using the sorted array as input.
Make one and only one graph that include the plot for all of the runs using Excel or LibreOffice|OpenOffice Calc or any other tool that plots graphs as indicated. First plot the elapse time of the 100 runs with the unsorted array that was generated using the uniform distribution method provide by StdRandom. Second, plot the elapse time of the runs with the partially sorted array. Third, plot the elapse time of the runs with the sorted array.
The book from which to get the source code is Sedgewick, R. & Wayne, K., Algorithms (4th ed.)