( The codes below do not have to be changed, just write the code for the question that compiles with the codes given below) 

In Topic 4, code has been provided for Insertion Sort, Shell Sort and Quick Sort algorithms . 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 significantly 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:

Proposed experimental procedure: 2 marks

Code for counting operations in search methods: 2 marks

Code for creating random arrays: 3 marks

Code for running experiments, including timing: 3 points

Details of experiments and results: 7 marks

Final conclusions & comparisons with theory: 3 marks

For the code (Items 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 Item 5, your experiments must be comprehensive, convincing, and fully described.

Note 1:

In fact, I provided two separate implementations of Insertion Sort: one in InsertSort.java 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 arr2[] = (String[])arr.clone();

Note 3:

Javas Math.random() 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).

 InsertSort Code 

import javax.swing.JOptionPane; 

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 <= last; toSort++) { Comparable toSortElement = a[toSort]; System.out.println("Checking " + a[toSort] + " at pos " + toSort); // Go back through the list to see how far back (if at all) // this element should be moved. // Note: we assume all elements before this are sorted relative // to each other. boolean moveMade = false; // Minor optimisation, also used in messages displayed index = toSort - 1; while ((index >= 0) && (toSortElement.compareTo(a[index]) < 0)) { // Shuffle elements over to the right, put firstUnsorted before them System.out.println("Moving forward " + a[index] + " from pos " + index); a[index+1] = a[index]; index--; moveMade = true; } if (moveMade) { System.out.println("Inserting " + toSortElement + " at pos " + (index+1)); a[index+1] = toSortElement; } else { System.out.println("Leaving " + toSortElement + " at pos " + (index+1)); } } } /** Main method to test insertionSort */ public static void main(String[] args) { String arr[] = {"W","B","Z","Q","M"}; //Integer arr[] = {12, 17, 3, 2000, 2001, 99, 203}; /* String arr[] = {"a", "hello", "x", "w", "q", "h", "d", "p", "a1", "x2", "w2", "q1", "2h", "2d", "3p", "1a", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "q3x", "q2w", "3qq", "qh4", "ad4", "4ap", "3aa", "3ax", "a5w", "q5", "fh5", "fd5", "fp5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "q3x", "q2w", "3qq", "qh4", "ad4", "4ap", "3aa", "3ax", "a5w", "q5", "fh5", "fd5", "fp5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "q3x", "q2w", "3qq", "qh4", "ad4", "4ap", "3aa", "3ax", "a5w", "q5", "fh5", "fd5", "fp5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5", "g3x", "g2w", "f3q", "fh4", "gd4", "f4p", "f3a", "d3x", "s5w", "sq5", "sh5", "dd5", "sp5"}; */ JOptionPane.showMessageDialog(null, "Array length is "+ arr.length); JOptionPane.showMessageDialog(null, "Array before sorting: " + array2String(arr)); insertionSort(arr); JOptionPane.showMessageDialog(null, "Array after sorting with Insertion Sort: " + array2String(arr)); System.exit(0); } /** utility method to return string representation of array of strings */ private static String array2String(Object[] a) { String text="["; for (int i=0; i 
 
 
ShellSort Code 
 
 
 
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 < gap; first++) { insertionSort (arr, first, last, gap); } } // end for } // end shellSort /** Helper function for shellSort method, that sorts a subarray * that goes from the first to last index, in steps specified by gap. */ private static void insertionSort(Comparable[] a, int first, int last, int gap) { 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. // NOTE: Instead of considering a full array of adjacent elements, we are considering // a sub-list of elements from 'first' to 'last, separated by 'gap'. All others are ignored. // // Work forward through the list, starting at 2nd element, // and sort each element relative to the ones before it. for (toSort = first+gap; toSort <= last; toSort += gap) { Comparable toSortElement = a[toSort]; // Go back through the list to see how far back (if at all) // this element should be moved. // Note: we assume all elements before this are sorted relative to each other. boolean moveMade = false; index = toSort - gap; while ((index >= first) && (toSortElement.compareTo(a[index]) < 0)) { // Shuffle elements over to the right, put firstUnsorted before them a[index+gap] = a[index]; index = index - gap; moveMade = true; } if (moveMade) { //System.out.println("Inserting " + toSortElement + " at pos " + (index+1)); a[index+gap] = toSortElement; } } } /** Version of insertionSort method that uses the correct settings to sort an entire array * from start to end in steps of 1. * * This version uses the 'helper function' version, but is a direct substitute for the * quickSort() method call. */ public static void insertionSort(Comparable arr[]) { insertionSort(arr, 0, arr.length-1, 1); } /** Main method to test shellSort */ public static void main(String[] args) { String[] arr = {"aa", "xa", "bq", "aq", "sw2", "ph", "pp"}; // Going to sort a copy of the array, not the original. // Note that it is NOT sufficient to say "String[] copy = arr;" as this // just copies a new reference to the same array in memory. // we can also use insertionSort directly String copy2[] = arr.clone(); JOptionPane.showMessageDialog(null, "Array length is "+ copy2.length); JOptionPane.showMessageDialog(null, "Array before sorting with InsertionSort " + array2String(copy2)); insertionSort(copy2); JOptionPane.showMessageDialog(null, "After Sorting with InsertionSort: " + array2String(copy2)); String copy[] = arr.clone(); JOptionPane.showMessageDialog(null, "Array before sorting with Shell Sort: " + array2String(copy)); shellSort(copy); JOptionPane.showMessageDialog(null, "After Shell Sort" + array2String(copy)); System.exit(0); } /** utility method to return string representation of array of strings */ private static String array2String(String[] a) { String text="["; for (int i=0; i 
 
 
 
 
QuickSort Code 
 
 
 
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 < 2) return; // the array is already sorted in this case quickSortStep(arr, c, 0, arr.length-1); // call the recursive sort method } /** QuickSortStep method: * Method called by QuickSort(), which sorts the elements of array s between * indices leftBound and rightBound, using a recursive, in-place, * implementation of the quick-sort algorithm. **/ private static void quickSortStep (Object[] s, Comparator c, int leftBound, int rightBound ) { if (leftBound >= 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 <= downIndex) { // scan right until larger than the pivot while ( (upIndex <= downIndex) && (c.compare(s[upIndex], pivotValue)<=0) ) upIndex++; // scan leftward to find an element smaller than the pivot while ( (downIndex >= upIndex) && (c.compare(s[downIndex], pivotValue)>=0)) downIndex--; if (upIndex < downIndex) { // both elements were found temp = s[downIndex]; s[downIndex] = s[upIndex]; // swap these elements s[upIndex] = temp; } } // the loop continues until the indices cross int pivotIndex = upIndex; temp = s[rightBound]; // swap pivot with the element at upIndex s[rightBound] = s[pivotIndex]; s[pivotIndex] = temp; // the pivot is now at upIndex, so recursively quicksort each side quickSortStep(s, c, leftBound, pivotIndex-1); quickSortStep(s, c, pivotIndex+1, rightBound); } /** Main method to test QuickSort */ public static void main(String[] args) { //String arr[] = {"5", "3", "2", "6"}; String arr[] = {"This", "is","yet", "another", "Boring", "Array", "Sorting", "test"}; JOptionPane.showMessageDialog(null, "Array before sorting: " + array2String(arr)); // quickSort method's first parameter is just the array; // second is a newly created string comparator object (class defined later in this file) quickSort(arr, new StringComparator()); JOptionPane.showMessageDialog(null, "Array after sorting: " + array2String(arr)); } /** utility method to return string representation of array of strings */ private static String array2String(String[] a) { String text="["; for (int i=0; i