Sorting Algorithm Analysis

HOW TO DO " 2. Code for counting operations in search methods: 2 marks "

INSERTION SORT: /** This is extracted from code in the ShellSort class. * It is slightly simpler than the insertionSort in the ShellSort class because * it does not use the startpoint, endpoint and gap. */ import javax.swing.JOptionPane; public class InsertSort { /** * Insertion Sort method: this one sorts an array from its start to its end. * (You cannot specify a start point, end point or gap.) */ private static void insertionSort(Comparable[] a) { int index; // general index for keeping track of a position in array int toSort; // stores the index of an out-of-place element when sorting. int last = a.length-1; // Work forward through the list, starting at 2nd element, // and sort each element relative to the ones before it. for (toSort = 1; toSort = 0) && (toSortElement.compareTo(a[index])  
SHELL SORT:
 
/** Based on code from Carrano & Savitch, Data Structures and Abstractions with Java
 
 * With some simplifications for clarity, an extra insertionSort method, * and test code at the end. */ import javax.swing.JOptionPane; public class ShellSort { /** Task: Sorts equally spaced elements of an array into ascending order. * The paramater arr is an array of Comparable objects. */ public static void shellSort (Comparable[] arr) { int last = arr.length-1; // Begin with gap = half length of array; reduce by half each time. for (int gap = arr.length/2; gap > 0; gap = gap/2) { if (gap % 2 == 0) gap++; // if gap is even, move to next largest odd number // Apply Insertion Sort to the subarrays defined by the gap distance for (int first = 0; first = first) && (toSortElement.compareTo(a[index])  
QUICK SORT:
 
/** Based on code from Goodrich & Tamassia, Data Structures and Algorithms in Java * With some simplifications for clarity, and test code at the end. */ import javax.swing.JOptionPane; import java.util.Comparator; public class QuickSort { /** QuickSort method: * Sorts the elements of array arr in nondecreasing order according * to comparator c, using the quick-sort algorithm. Most of the work * is done by the auxiliary recursive method quickSortStep. **/ public static void quickSort (Object[] arr, Comparator c) { if (arr.length = rightBound) return; // the indices have crossed Object temp; // temp object used for swapping // Set the pivot to be the last element Object pivotValue = s[rightBound]; // Now partition the array int upIndex = leftBound; // will scan rightward, 'up' the array int downIndex = rightBound-1; // will scan leftward, 'down' the array while (upIndex = upIndex) && (c.compare(s[downIndex], pivotValue)>=0)) downIndex--; if (upIndex   The purpose of this assignment is to analyse the performance of sorting algorithms experimentally, to complement the theoretical analysis presented in lectures. In Topic 4, code has been provided on Blackboard for Insertion Sort, Shell Sort and Quick Sort algorithms (among others). Starting with this code (not any other), perform a sequence of experiments to compare the performance of the three algorithms on arrays of different sizes. You should follow these steps: Put the methods for all three sorting algorithms into one class (see Note 1), along with a main) method that defines an unsorted array, and passes a clone to each sorting method (see Note 2). Modify the code for each sorting method to count the number of both 'move' and 'compare' operations (two separate counts). You could use a class member variable that you initialise to 0 and then increment every time an array element changes position (for 'move) or is compared with another one or with some fixed value (for 'compare). Write a method that returns a reference to an array of objects such as Strings or Integers, with the size of the array specified as a parameter to the method. Each object in the array must be initialised to a random value (see Note 3). Write code to create arrays of various sizes, sort each array using all sorting methods, and record/display the number of operations each sorting method requires. You might need to average multiple runs at a single size. As well as counting operations, include code to measure the time (in milliseconds) taken by each sorting algorithm on each array. Make sure to try large enough array sizes so that the time is significanty greater than 0 milliseconds. Plot the results, showing for each array size what averages of both time and number of operations are. As discussed in lectures, the performance of Shell Sort can be improved dramatically by ensuring the gap is always an odd number, this is implemented in the code on Blackboard. Locate the line of code that ensures the gap is an odd number, comment it out, and re-evaluate the performance of Shell Sort without this feature Comment on how your results compare to the theoretical complexity results for sorting algorithms that are presented towards the end of the slides for Topic 4 (Sorting Algorithms). You must submit a report with: Your experimental procedure, including details of all changes you made to the code (for example, by providing excerpts of the relevant code with your changes highlighted) Your analysis and results, including appropriate tables and plots for all of the algorithms tested Refer to the steps above and the marking scheme below for further understanding of what your report should include. The following marking scheme will be used: 1. Proposed experimental procedure: 2. Code for counting operations in search methods: 3. Code for creating random arrays: 4. Code for running experiments, including timing 5. Details of experiments and results: 6. Final conclusions & comparisons with theory: 2 marks 2 marks ma points 7 marks 3 marks For the code (ltems 2-4), program style will NOT be considered this week; all that is required is that you have written code that works correctly. The most important element of this assignment is what experiments you perform and what conclusions you draw from them. To get full marks for ltem 5, your experiments must be comprehensive, convincing, and fully described. Note 1: In fact, I provided two separate implementations of Insertion Sort: one in InsertSortjava and the other in ShellSort java. For this assignment, use the one in ShellSort,java. Note 2: To ensure comparisons are fair, you will need to have each method sort the same array. However, will first need to clone the array; otherwise, the second method will get an already-sorted array. For example, to clone an array of strings called arr into a new array, arr2: String arr20 (String[])arr.clone0; Note 3: Java's Math.random0 method provides an easy way of creating random double values in the range 0.0-1.0. However, an array of doubles is no good for our sorting methods, since they work with Objects. The solution is to convert each random double value into an Object: you could convert it into a String or create objects of a type-wrapper class such as Double or Integer and initialise them with the random values (scaled if appropriate)