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.

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