CIT 594 Squaresort
Spring 2015, David Matuszek
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 (
n) arrays. (Since
n may be different, this should really be called
squaresort is more euphonius.) These arrays will be sorted according to more than a single criteria.
We will define an
A to be "sorted" if, for all row numbers
and all column numbers
, it is the case that
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
n. Do some timings of your method to determine the actual Big-O running time.
java.util.Comparator interface to squaresort objects in more than one way.
Write up your results.
Create a project
Squaresort, and in it, a package
squaresort. Your package should contain (at least) the following classes:
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
. For convenience, the fields
employeeId are all
public, so you don't need getters. For safety, they are all
final. The methods
toString are all provided.
Write the following methods. Test each method as you go with JUnit 4, preferably using TDD.
public static void linearSort(int nums)
numsin 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)
Personobjects according to the given
Comparator. (See the Java API for
java.util.Comparatorfor 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)
public class NameComparator implements Comparator<Person>
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
Comparator) interface, you can use the
compareTomethod in the
public class PayGradeComparator implements Comparator<Person>
public int compare(Person p1, Person p2), which compares two Person objects by their pay grades.
public class EmployeeIdComparator implements Comparator<Person>
public int compare(Person p1, Person p2), which compares two Person objects by their employee ids.
AllTestsis a JUnit test suite; Eclipse can generate it for you.).
Please be sure that assertions are enabled when you turn in your project.
Turn in a
readme file in any widely understood format (
squaresort, including loop invariants as appropriate.
n), and some timings that back up your claim.