COMSC 111 Lab 8 This lab is based on David Levine's Sort Detective lab developed at St. Bonaventure University, included in SIGCSE’s Nifty Assignments (http://nifty.stanford.edu). Professor Cates...

You have been given a program that sorts an array using one of five sorting algorithms.


COMSC 111 Lab 8 This lab is based on David Levine's Sort Detective lab developed at St. Bonaventure University, included in SIGCSE’s Nifty Assignments (http://nifty.stanford.edu). Professor Cates didn’t learn her lesson from Lab 3 and once again outsourced to the lowest bidder. You have been given a program that sorts an array using one of five sorting algorithms. The algorithms are (in alphabetical order): • bubble sort • insertion sort • merge sort • quick sort • selection sort While the sorting algorithms were implemented correctly, they were not labeled properly in the finished product. Instead they are identified with Greek letters. It is your job to match each button with its proper label using what you know about the sorting algorithms. For reference, the code for each algorithm is included at the bottom of the lab instructions There are several parameters and outputs which will help you • List properties: you can create a list of random, already sorted, nearly sorted, or reverse sorted elements. • List size: you can also adjust the length of the list to be sorted (N). • Comparisons: the total number of times a value in the array was compared during the entire sorting process. • Movements: the number of times an element in the array was moved. A swap of two elements counts as three movements. • Time: the time the sorting algorithm took to run. Note: this measurement will be noisy! You may work with a partner on this lab, if you choose. If you work with a partner submit only one write-up with both names (either group member may submit). Instructions: 1. First download the .zip. Unzip it by right clicking, and selecting Extract All(do not just double click on the zip file) and you should get a folder named COMSC111Lab8. In that folder, run (double click) COMSC111Lab8.jar. 2. Next devise a plan to match each algorithm to the button labels, e.g., insertion sort to Alpha. Hint: It may make sense to try to divide the sorts into initial groups based on run-time performance (O(n2) vs O(n log n)) and then work on each group separately. Once you have the algorithms grouped by time complexity, then consider the relative numbers of movements and comparisons. Which algorithms perform more movements and which perform more comparisons? How does having an already sorted list affect the number of movements and comparisons? 3. Then implement your plan. Be sure to save all of your results. You must present your results using at least one but probably several tables or graphs. 4. Finally, write up your findings in a lab report. What to turn in A written report including the following three sections 1. Methods: A description of your experimental design (your plan to match the algorithms to the labels). 2. Results: The results you obtained. This section should include the tables and graphs. It may not have very much writing. 3. Discussion: A discussion of your results in which you tell me your conclusions (which algorithm matches with which label) and how you have arrived at your conclusions. Include a summary table showing your mapping from button name to algorithm so it is easy for me to identify your conclusions. Your submission should be either a Word document or pdf file. Grading There is no coding in this lab. Therefore a significant portion of the grade will be based on the quality of your written report. This includes completeness, clarity, and general presentation (neatness). Conciseness is a virtue. Write enough to clearly explain your plan and results, but no more. Do not write more for the sake of making your report longer. Grade breakdown is as follows: Correctly matching the algorithms: 5 points Documentation of results: 10 points Explanation: 10 points //Selection Sort public void selectionSort(int list[]) { for (int j=list.length-1; j>0; j--) { int maxpos = 0; for (int k=1; k<=j; k++)="" {="" comparisons++;="" if="" (list[k]="">list[maxpos]) { maxpos = k; } } if (j != maxpos) { movements += 3; int temp = list[j]; list[j] = list[maxpos]; list[maxpos] = temp; } } } //Insertaion Sort public void insertionSort(int list[]) { for (int j=1; j 0 && list[k-1]>temp ) { comparisons++; movements++; list[k] = list[k-1]; k--; } if (k > 0) { comparisons++; } movements++; list[k] = temp; } } //Bubble Sort public void bubbleSort(int list[]) { int temp; do { movements++; temp = list[0]; for (int j=1; jlist[j]) { movements += 3; temp = list[j]; list[j] = list[j-1]; list[j-1] = temp; } } comparisons++; } while (temp != list[0]); } //Quicksort public void quickSort(int list[]) { qsort(list, 0, list.length-1); } private void qsort(int list[], int low, int high) { if (low temp); do { i++; comparisons++; } while (list[i] < temp);="" if="" (i="">< j)="" {="" movements="" +="3;" int="" swaptemp="list[i];" list[i]="list[j];" list[j]="swapTemp;" }="" else="" {="" return="" j;="" }="" }="" }="" merge="" sort="" public="" void="" mergesort(int="" list[])="" {="" msort(list,="" 0,="" list.length-1);="" }="" private="" void="" msort(int="" list[],="" int="" low,="" int="" high)="" {="" if=""><= mid)="" &&="" (j=""><= high))="" {="" comparisons++;="" if="" (list[h]=""><= list[j])="" {="" movements++;="" otherlist[i]="list[h];" h++;="" }="" else="" {="" movements++;="" otherlist[i]="list[j];" j++;="" }="" i++;="" }="" if="" (h="">mid) { for (int k=j; k<=high; k++)="" {="" movements++;="" otherlist[i]="list[k];" i++;="" }="" }="" else="" {="" for="" (int="" k="h;"><=mid; k++)="" {="" movements++;="" otherlist[i]="list[k];" i++;="" }="" }="" for="" (int="" m="0;">