COMP202 Data Structures and Algorithms Assignment 5 Solved

 
This programming assignment will test your knowledge and your implementation abilities of what you have learned in the Sorting parts of the class.

This homework must be completed individually. Discussion about algorithms and data structures are allowed but group work is not. Any academic dishonesty, which includes taking someone else’s code or having another person doing the assignment for you will not be tolerated. By submitting your assignment, you agree to abide by the Ko¸c University codes of conduct.

Description
This assignment requires you to implement various sorting algorithms. These algorithms include insertion sort, heap-sort, quick-sort, merge-sort and counting sort.

The files provided to you have comments that will help you with implementation.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.

1

•   SortGrade.java: This file grades your sorting implementations with different data distributions and data sizes. It checks aforementioned methods for certain algorithms 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. If you are getting sorted elements but swaps and compares do not match, make sure to finish the rest of the homework and come back to the issue.

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