Description

In this assignment you will implement a number of common sort algorithms and compare their performance for different input files. You will also write JUnit tests to test your code.
Total points for this assignment: 200 (100 automatic, 100 marked by demonstrators)
The following will be marked:
1. Correctness of your results (eg items are sorted), JUnit tests, and test code coverage – automatic mark through web-cat, 100 points
2. Correct implementation of sort algorithms (eg your MergeSort method implements merge sort rather than another kind of sort) and results of running time comparisons – marked by demonstrators, 100 points
Submission and automatic marking is through https://webcat.scss.tcd.ie/cs2012/WebObjects/WebCAT.woa. Submission of final version both through Web-CAT and Blackboard.
Late assignments will be deducted 40 points per day
Please submit only SortComparison.java and SortComparisonTests.java. Do not submit input files.

Assignment specification
1. Implementation
Download SortComparison.java file.
Write a java class SortComparison in SortComparison.java file (please do not use custom packages as web-cat will give an error) which should implement the following methods
• static double[] insertionSort (double a[]);
• static double[] selectionSort (double a[]);
• static double[] quickSort (double a[]);
• static double[] mergeSort (double a[]);
In each of the methods parameter a[] is an unsorted array of doubles. Each method should sort the elements in ascending order and return a sorted array. Each method should implement a different sorting algorithm, specified in method name. Note that for some of the algorithms you will need to add additional methods apart from the ones listed above. It is up to you whether to implement basic versions of the algorithms, or add additional improvements as discussed in lectures.

2. Testing

Download SortComparisonTest.java file.
Write a java class SortComparisonTest in SortComparisonTest.java file, which should implement JUnit tests for SortComparison.
Your goal is to write enough tests so that:
• Each method in SortComparison.java is tested at least once,
• Each decision (that is, every branch of if-then-else, for, and other kinds of choices) in SortComparison.java is tested at least once,
• Each line of code in SortComparison.java is executed at least once from the tests.
The submission server will analyse your tests and code to determine if the above criteria have been satisfied.

3. Algorithm performance comparison
Create a main method in SortComparisonTest that runs all the experiments on SortComparison described below and prints the time in milliseconds that each method execution took. This method will not run on the submission server, but you should run it locally on your computers. You need to record the results in a comment at the top of your SortComparisonTest file.
Your experiments in this section should be run from within the provided main method. Do not run these experiments from within a jUnit test.
The following input files are available for download from Blackboard:
• numbers1000.txt – contains 1000 random decimal numbers, one per line
• numbers1000Duplicates.txt – contains 1000 random decimal numbers, one per line, but those 1000 consist of only up to 100 unique ones
• numbersNearlyOrdered1000.txt – contains 1000 decimal numbers, one per line, where most of the numbers are in correct ascending order, with approx. ~6% of the numbers out of place
• numbersReverse1000.txt – contains 1000 decimal numbers, one per line, sorted in reverse (ie descending) order
• numbersSorted1000.txt – contains 1000 decimal numbers, one per line, sorted in ascending order
• numbers10000.txt – contains 10000 decimal numbers, one per line, in random order

In the comment at the top of your SortComparisonTest record the time it took to execute each of 4 methods implementing 4 different sorting algorithms, for each of 7 different input files, containing different size and type of input. Run each experiment 3 times and record the average running time. Your results should be displayed in a format that enables easy comparison per algorithm and per data type, for example, as in the table below.

Insert Selection Quick Merge
100 random
1000 random
1000 few unique
1000 nearly ordered
1000 reverse order
1000 sorted
10000 random

For fun:
This part will not be marked, but if you are curious you could also try the following:
1. Add counters to sort methods that count the number of value comparisons, and value swaps for each of the sort algorithms, to compare the numbers of each per algorithm, to see where the performances gains come from

2. Implement a multi-threaded version of merge sort and compare its performance to singlethreaded one.

Appendix: reminder of general assignment instructions from Semester 1
Please see a walkthrough on how to submit an assignment on Web-CAT.
For security reasons the submission server is only accessible from the campus network. If you want to access it from home you need to connect to the campus network via a Virtual Private Network (VPN) with your SCSS account. Instructions.
If you are having trouble with assignments then you can attend both lab hours, which will give you more contact hours with teaching staff. If you are seeking support with more basic Java programming you can additionally attend the Undergraduate Programming Centre.
• Write your name next to @author at the beginning of each file
• Write the names of people you discussed this assignment with under the @author line. Do not share code and do not write code for others!
• You need to adequately test each method in your source code by adding sufficient jUnit tests
• Do not import data structures from the java libraries.
• The submission server for this assignment will open shortly.