COMP202 - Data Structures and Algorithms - Assignment 5 - Solved

This assignment requires you to implement various sorting algorithms. These algorithms include insertion sort, heap-sort, quick-sort, merge-sort and counting sort. In addition, you are given the chance to submit another sorting algorithm to enter a sorting competition for bonus points.

The files provided to you have comments that will help you with implementation. In addition, keep the slides handy as they include the pseudo-codes for the algorithms. The file descriptions are below. Bold ones are the ones you need to modify and they are placed under the code folder, with the rest under given.

•    AbstractArraySort.java: This file describes the abstract sorting class which the other sorting algorithms extend. It defines the sort method which is the primary function you should overwrite. It also has the swap and compare methods that you need to call in the concrete classes whereever applicable. Hint; not all algorithms utilize swap. It also has other utility methods which might be of use in debugging.

•    JavaArraySort.java: A wrapper class for the Java’s default sorting method. You can take a look if interested.

•    InsertionSort.java: Implement the insertion sort algorithm in this file. Remember to use the swap and compare methods from the abstract parent class whereever applicable.

•    HeapSort.java: Implement the heap-sort algorithm in this file. Remember to use the swap and compare methods from the abstract parent class whereever applicable. Make sure to fill out the heapify method which will also be graded.

•    QuickSort.java: Implement the quick-sort algorithm in this file. Remember to use the swap and compare methods from the abstract parent class whereever applicable. Make sure to fill out the partition method which will also be graded. You have two options for this, either version which returns an indexPair object to return two indices or comment this out and uncomment the version which returns an integer.

•    MergeSort.java: Implement the merge-sort algorithm in this file. Remember to use the swap and compare methods from the abstract parent class whereever applicable. Make sure to fill out the merge method which will also be graded.

•    CountingSort.java: Implement the counting sort algorithm in this file. Note that you need to do this only for integers. You do not have to use any function from its parent in this class.

•    SortDebug.java: This file has a smaller main function which you can use to debug individual sorting algorithms. We suggest that you test your implementations here first.

•    SortGrade.java: This file grades your sorting implementations with different data distributions and data sizes. It checks aforementioned methods for certain algorithm and tests whether your implementations sort the data correctly. In addition to integers, doubles and strings are also utilizied. The code also checks for number of swaps and compares for three algorithms. Small implementation details might result in slightly different numbers and we might update the autograder to reflect this so do not spend too much time on this and come back to it after you are getting an 88.

•    DataGenerator.java: This file has the code to generate data to test your implementations. Take a look at it if interested but you do not need to worry about it.

Bonus: Sorting Spree!

This homework includes a bonus component where your sorting algorithm will compete with the rest of the class to receive a bonus up to 30 points. Your bonus grade will depend on how well you do in the benchmarking as compared to other submissions. The exact grading scheme will be announced later. The files you need to look at for this part are below. You are free to submit any one of the implementations you have already done but we suggest to try at least one of the hybrid algorithms we have seen.

•    ContestEntrySort.java: This file should have your competition entry sorting algorithm. You do not need to use anything from the parent class apart from overriding the sort method. You are not allowed to use an existing sorting library such as Java’s own method.

•    SortBenchmark.java: This file benchmarks the given algorithms. We are going to use something similar but will also add doubles and strings. Your score will depend on a weighted average of your sorting times, smaller the better. If you are interested in the bonus, go over this file.

•    benchmarkLog.java: This file stores the benchmark performances and calculates statistics.