Sorting Algorithm Analysis HOW TO DO \" 2. Code for counting operations in searc

Question

Sorting Algorithm Analysis

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

SHELL SORT:

/** Based on code from Carrano & Savitch, “Data Structures and Abstractions with Java”

QUICK SORT:

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).

Explanation / Answer

Dear Student,

I am assuming that you know how these sorting algorithms work.If not, please check them out first on youtube or other sources where you can get a feel of their working.Here the count that you are required to give is of number of camparisons and number of moves in the array you have to do in order to sort it.So you have to modify each sort's code to get these moves and comparisons.

So define two member variables in the class which contains these 3 sorts. 1)comparisons 2)moves and initialize both to 0.

Then increment each when a comparison or move is made(modify code accordingly in all sorts).

Example:In InsertSort above

The code in BOLD is the extra lines of code added.

If the element under consideration reaches to first place then moves will be same as comparisons otherwise comparisons will be one more than moves in all other cases(for insertion sort).

Likewise you will have to understand other sorts-how they work,where does comparison take place and when we swap or move elements then it would become easy to modify the code accordingly.

Thanks :)

Feel free to ask in case of any query!

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.