Language: JAVA

Your task is to create one package software in JAVA with methods for four 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

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, , and then call one of the sorting methods and time the method. After that, your software should print the time it took the computer to sort the array using that technique. Your software will repeat the time trial 100 times.

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 sizes, 10,000; 100,000; and 1,000,000 elements for each sorting method.

This means you will run your program 12 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 of the 12 runs, 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 will 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 from the 12 runs. The exact organization or format is up to you.

You will have 12 sets of results one for each sorting method for each size, But you will not have data for all 12 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.