In this exercise you’ll get an intuition for what happens when we use algorithms with different computational complexities to solve the same problem. Download these two sorting programs from the class website: SelectionSort, MergeSort.These programs test the specified sorting algorithm on an array whose size is specified by the user, then outputs the amount of time the sorting algorithm takes.
For each sorting program, the main method first prompts for the size of the array to be sorted, then reads the actual integers into the array.Modify the main method of each program so that the values in the array come not from the keyboard, but from calling Math.random() or other random number generator. (Note: Math.random() returns a value of type double in the range 0.0 <= value <= 1.0, but it’s easy to scale and convert this to an integer).Also: add a prompt asking the user if the entire sorted array should be output. If the user says no, modify the appropriate loop to output just the first 100 elements, so we can check that they really are sorted.
For large arrays you don’t want to wait while everything prints!Make a table showing the time it takes (in seconds) to perform sorts for each of these array sizes. Do this for both programs.1000
5000
10,000
50,000
100,000
500,000
1,000,000 (this may take several minutes for some programs – patience – but if it takes more than 5 minute on your computer you can terminate it)The smaller sorts will seem to complete instantaneously, while some algorithms will take quite some time as the input size gets large.
Note: when timing a program running on a computer, don’t run any other programs.Turn in your completed table.
Turn in your written results at the beginning of class on the due date.(8 points) Continue the work you began in Lab 1 with these three sorting programs: BubbleSort, InsertionSort, and QuickSort. Modify each program’s main method as before to 1) create an array of random values to sort, and 2) prompt the user about outputting the sorted array values. Run the same trials as before and record the results along with the timings you did for Lab 1:
1000
5000
10,000
50,000
100,000
500,000
1,000,000 (this may take several minutes for some programs – patience)
(2 points) Sketch two graphs showing the data from each table. Plot the timings for BubbleSort, InsertionSort, and SelectionSort on one; MergeSort and QuickSort on the other.
(2 points) Add a second array to be sorted to the main method in the QuickSort class and fill this array with values already in sorted order before calling quickSort. Run the program again on the same array sizes as in Problem 2. Create a new table showing a side-by-side comparison of QuickSort’s performance on random data versus sorted data. If the program should fail for any reason, speculate as to why and determine (within a multiple of 1000) the smallest size array that causes it to fail.
(2+2+2) Determine the runtime complexity of each of the following three methods. Express your answer first exactly, then as a Big-O estimate.
void oddOnes(double[] data) {
for (int i=1; i<data.length; i+=2) {
data[i] = 1;
}
}double findRoots(double a, double b, double c) {
double result = b * b – 4 * a * c;
double disc = Math.sqrt(result);
double[] result = {(-b + disc) / (2 * a), (-b – disc) / (2 * a)};
return result;
}void initPixels(Color[][] pixels, int pixelRows, int pixelCols, Color c) {
int row, col;
for (row = 0; row < pixelRows; row++) {
for (col = 0; col < pixelCols; col++) {
pixels[row][col] = c;
}
}
}
(2 points) The first three orders of algorithms discussed in the text are linear, logarithmic, and quadratic. Which of these three best describes the average-case behavior of BinarySearch?
