The University of Western Australia
School of Computer Science and Software Engineering
 
 

School of Computer Science and Software Engineering

CITS2200 Data Structures and Algorithms

These exercises are worth 2.5% of your final grade and are due at 11:59pm, Friday, March 13, 2020

I will cover the sorting algorithms this week, you may watch the videos linked below as well:

In this lab you are required to implement a number of sorting algorithms. You should download the package CITS2200.jar and write a class, Sorter that implements the methods specified in in the interface Sort. The class must be in a file called Sorter.java and a template is provided, with the mergesort method already completed.

The work you submit must be your own work, and you are not permitted to work with anyone, help anyone write code, or debug anyone elses code. You may use the help forum if you require assistence, however you should not post source code, or look at anyone elses source code. The submissions will be thoroughly checked for evidence of collusion and plagiarism.

The Sort class requires you to implement three different methods for sorting an array of long integers. These methods are InsertionSort, QuickSort and MergeSort (already implemented). You must also implement a counting method to compare the number of array assignments each sorting method used. The Sorter class should mainatin a private variable count that is incremented every time an array assignment is performed (eg arr[i]=x;). The reset() method sets the count variable to 0, and getCount() returns its current value. This allows you to see the relative amount of work each method does. The descritpion of the algorithms follows:

Note that as an automated marker is used you will not be able to include print statements, java.util classes etc in your implementation. However, a test class is available for your convenience.

Submit only the file Sorter.java to cssubmit. There is an automated script that will compile and run your code, and estimate your final mark. This feedback ensures that you will not lose marks for small errors, but is no substitute for your own thorough testing. You may submit as many times as you like.

Sample solution for Lab1Lab 1 solution

This Page