This is a java program, base on the code provided down below, do PART 2. thanks

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

Here is the code:

import java.util.*; public class sort { public static void main(String args[]) { int size = 10000; //change this line to change the size of the array Random random = new Random(); int arr[] = new int[size]; int temp[] = new int[arr.length]; ArrayList list= new ArrayList(); //Repeating the experiment 100 times System.out.println("**************Quick Sort************** "); for(int i=0;i<100;i++) { for(int j=0;j low) { int mid = (low + high) / 2; mergeSort(a, temp, low, mid); mergeSort(a, temp, mid + 1, high); merge(a, temp, low, mid, high); } } static void merge(int[] a, int[] temp, int low, int mid, int high) { int lowP; for(lowP = low; lowP <= high; ++lowP) { temp[lowP] = a[lowP]; } lowP = low; int highP = mid + 1; int aP; for(aP = low; lowP <= mid && highP <= high; ++aP) { if (temp[lowP] <= temp[highP]) { a[aP] = temp[lowP]; ++lowP; } else { a[aP] = temp[highP]; ++highP; } } int i; if (lowP > mid) { for(i = highP; i <= high; ++i) { a[aP] = temp[i]; ++aP; } } else { for(i = lowP; i <= mid; ++i) { a[aP] = temp[i]; ++aP; } } } //insertion sort static void insertionSort(int[] a) { for(int i = 1; i < a.length; ++i) { int currentElement = a[i]; int j; for(j = i - 1; j >= 0 && a[j] > currentElement; --j) { a[j + 1] = a[j]; } a[j + 1] = currentElement; } } //selection sort static void selectionSort(int[] a) { for(int i = 0; i < a.length - 1; ++i) { int currentMin = a[i]; int currentMinIndex = i; for(int j = i + 1; j < a.length; ++j) { if (currentMin > a[j]) { currentMin = a[j]; currentMinIndex = j; } } if (currentMinIndex != i) { a[currentMinIndex] = a[i]; a[i] = currentMin; } } } }

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

Part 1 -- the Software and the Experiment

You will conduct experiments timing sorting techniques to see how their actual performance compares to predicted results. (You will also be comparing iterative sorting techniques to recursive sorting techniques.)

Your task is to create one software package with methods for four different sorting techniques and to conduct time trials comparing the temporal efficiency of the four techniques. The four techniques are:

1. Selection Sort
2. Insertion Sort
3. Quick Sort
4. Merge Sort

You do not need to start from scratch sample software in the chapter includes the four techniques. Your task is to create a single program that will create an array of integers, load the array with random values between 1 and 100,000, (some of the sample software has code that does this), and then call one of the sorting methods to sort the random array. Your software repeats the process for one sorting method -- from filling the array with random numbers to completing the sort 100 times. only the sort should be timed. For each iteration, you should print the time it took the computer to sort the array using that technique.

Here is an outline of what your main method should do:

1. set the array size
2. create an integer array of that size
3. load the array with random values such that 0 < a[i] < 100,000
4. capture the system time
5. call a method to sort the array
6. capture the system time and calculate the elapsed time. This elapsed time will be how long it took to sort the array.
7. print the elapsed time in seconds.

Note: steps 2 through 7 should be in a loop that repeats 100 times.

You should test your software with arrays of different sizes. For iterative sorts you could try try, 10,000; 100,000; 200,000 and 1,000,000 elements for each sorting method. For the recursive sorts, try 100,000, 200,000, 1,000,000, 2,000,000 and 10,000,000. The exact sizes you try are up to you, but you should get some meaningful results.

This means you will run each program several times once for each size for each sorting technique. Your software should contain methods for all sorting techniques, but your main method only needs to call one method each time you run your program. (This is step 5, above.) You can comment out any calls to other methods. Note that some of the sorting techniques require more than one method -- for example, quick sort needs a quick sort method and a partition method. Your man method calls quick sort, which will call partition as needed.

As the note below the outline says, for each run of your program, your software should repeat the trial 100 times, printing the 100 times on the screen in a column, one time on each line. You should copy and paste the resulting data from each run into a column in an Excel spreadsheet. Then using Excel, you should determine the minimum, maximum and average run time for each run.

You should actually have two spreadsheets one where you will paste the 100 times with Excel functions at the bottom of the column to calculate the minimum, maximum, and average of the 100 times. These summary values can then be copied and pasted into a second spreadsheet where you will organize and display your summary results. The exact organization or format is up to you.

You will have several sets of results one for each sorting method for each size, But you will not have data for all runs if a run takes too long, say longer than 30 seconds or so stop the program manually and note that the method took longer than 30 seconds. This will happen, for example, with selection sort on 1 million items. When this happens, it is no longer necessary to continue with this method for larger data sets.

Part 2 The Analysis and the Report

Once you have your spreadsheet with the summary results, write a brief report about your work. Questions like these should be in your mind as you think about the experiment and the report: How does the time it takes for each algorithm to run compare to the size of the data set? What are the best case, worst case and average case times for each method for each array length? How does it fit with functions like T = f(n), T= f(n log(n) ) or T= f( n^2)? What does our book tell us about the time efficiency of these algorithms? Based on this, what did you expect the results to look like before running the time trials? How did the results compare with this? Which algorithm was the most efficient? Why was this more efficient than the others? You do not need to explicitly answer each of these questions, but they should guide you in considering what the experiment is all about.

Your report should include:

• a brief description of the topic what is this experiment all about? What do we hope to learn from it? Why is this important?
• a brief discussion of what you would expect to see in the experiment based on what you know about the sorting techniques before the experiment.
• a description of your experiment what did you do? What equipment and software did you use? Include the clock speed of your computer, and the specific compiler you used.
• a presentation of your results such as a table from the second spreadsheet with the summary results. If you can, create an Excel graph or set of graphs (one for each sorting technique) that illustrates your results.
• a commentary or analysis of results. What does the data show? How does this compare to what you expected? In particular, how do the iterative sorting methods compare to the recursive sorting methods?

You should be able to cut and paste the table with your summary results from Excel into Word for inclusion in your report.