CIT 594 Squaresort
Spring 2015, David Matuszek

Purposes of this assignment

• Give you experience determining Big-O running times
• Improve your understanding of loop invariants
• Make you think about algorithm design
• Teach the Comparator interface

General idea of the assignment

All the sorting techniques we have covered in class are for one-dimensional (linear) arrays. In this assignment you will develop a sorting technique for two-dimensional (m × n) arrays. (Since m and n may be different, this should really be called rectangularSort, but squaresort is more euphonius.) These arrays will be sorted according to more than a single criteria.

We will define an m × n array A to be "sorted" if, for all row numbers i < j < m and all column numbers k < l < n, it is the case that A[i][k] ≤ A[j][k] and A[i][k] ≤ A[i][l].

You won't be using any of the Java built-in sort methods, but will be writing your own. Provide (in // comments in the code) the loop invariants for each of the loops in your squaresort method. Use assert statements to implement your loop invariants.

Calculate the Big-O running time of your method, expressed in terms of m and n. Do some timings of your method to determine the actual Big-O running time.

Use the java.util.Comparator interface to squaresort objects in more than one way.

Write up your results.

In more detail

Create a project Squaresort, and in it, a package squaresort. Your package should contain (at least) the following classes:

• Person (supplied)
• Squaresort
• SquaresortTest
• NameComparator
• PayGradeComparator
• EmployeeIdComparator

Supplied code

The class Person.java has two constructors: new Person() will create a random Person object, while new Person(givenName, surname, payGrade) will create an employee with the given values. Each Person object has a unique int employeeId. For convenience, the fields givenName, surname, payGrade, and employeeId are all public, so you don't need getters. For safety, they are all final. The methods equals, hashCode, and toString are all provided.

Methods

Write the following methods. Test each method as you go with JUnit 4, preferably using TDD.

The Squaresort class

public static void linearSort(int[] nums)

This method simply sorts the array nums in place (that is, without creating any additional arrays), using any sorting method of your choice. Add the loop invariants, and the associated exit conditions, to this method as executable assertions.

public static void linearSort(Person[] people, Comparator<Person> comp)

Using the previous method as a model, this method sorts Person objects according to the given Comparator. (See the Java API for java.util.Comparator for information about Comparators, as well as my slides.) Add the loop invariants, and the associated exit conditions, to this method as executable assertions.

public static void squaresort(Person[][] people, Comparator<Person> comp)

This method sorts a rectangular (not ragged) array in place. By "sorted", I mean that every row and every column is sorted in ascending order.

It is likely that you will have some trouble figuring out how to do this. Try to invent an algorithm that works, probably by modifying some standard sorting algorithm. Of course, you will need to test your algorithm, because some of your ideas may not work out. You are allowed to discuss how to do this with other students (including on Piazza), but please try to solve the problem yourself first.

Add the loop invariants, and the associated exit conditions, to this method as executable assertions. These may also be somewhat difficult to determine.

 

Other classes

public class NameComparator implements Comparator<Person>

Contains the method public int compare(Person p1, Person p2), which compares two Person objects by their surnames (last name, in English) or, if the surnames are equal, by their given (first) names. Since names are Strings, and Strings implement the Comparable (not Comparator) interface, you can use the compareTo method in the java.lang.String class.

public class PayGradeComparator implements Comparator<Person>

Contains the method public int compare(Person p1, Person p2), which compares two Person objects by their pay grades.

public class EmployeeIdComparator implements Comparator<Person>

Contains the method public int compare(Person p1, Person p2), which compares two Person objects by their employee ids.

SquaresortTest, NameComparatorTest, PayGradeComparatorTest, EmployeeIdComparatorTest, and AllTests. (AllTests is a JUnit test suite; Eclipse can generate it for you.).

Please be sure that assertions are enabled when you turn in your project.

The writeup

Turn in a readme file in any widely understood format (.tty, .doc, .pdf, etc.). This file should contain:

• Estimates of how long you think this assignment will take you, and how long it actually does take you.
• An explanation of your algorithm for squaresort, including loop invariants as appropriate.
• How long you think your algorithm takes (in terms of Big-O, using m and n), and some timings that back up your claim.
• Your name.

Due date