Lab 5: Sorting

The goals of this week’s lab are to gain experience with

  • Java’s Comparator interface, and
  • sorting by various criteria.

PRE-LAB: Step 0

Before lab, please do the following:

  • Design document: As in prior labs, you should develop a design document before coming to lab.
  • Read the assigned pages from Chapter 6 (see the Readings page), and bring your questions to class.

Lab Assignment

In class, you will see how to implement the Comparable interface and how to write a compareTo method to compare two objects of the same class. While this is sufficient in many cases, sometimes we want to sort the same data in different ways. For example, we may wish to sort Student records by name in some situations and by grade point average in other situations. A single compareTo method is not sufficient to do this because compareTo only provides one way to sort such records.

In order to sort objects in multiple ways, the structure5 package uses the Java Comparator interface. A Comparator object’s sole purpose is to compare two objects of a given type and return a value indicating which one is “smaller”—in other words, which object comes before the other in the order imposed by the comparator. We can then sort in different ways by using different kinds of Comparator objects in the sorting algorithm. See Bailey Chapter 6.8—6.9 for a discussion of Comparators and how to use them.

In this lab we will develop an extension of Vector, called MyVector, that includes a method called sort. This sort method orders the elements of the Vector with the help of a Comparator. Here are the basic steps for implementing this new class:

Step 1: Get the code

Clone your private repository lab05-sorting. This repository contains starter files for MyVector.java and Student.java, plus newphonebook.txt and testphonebook.txt for the last part. The phone book is a few years old, so don’t expect to find yourself in it! Also, this file is not for public distribution. Note that testphonebook.txt is a smaller phone book to make testing easier during development.

Step 2: Implement MyVector.java

Fill in the class, MyVector, which is declared to be an extension of the structure5 Vector class. [footnote: 1] Since we are using generic structures, the class declaration for MyVector should begin:

public class MyVector<E> extends Vector<E>

You should write a default constructor for this class that simply calls super();. This will force the constructor in Vector (the parent/super-class of MyVector) to be called. This, in turn, will initialize the protected fields of the parent class.

Step 3: Implement sort

Inside MyVector.java, construct a new method called sort. It should have the following declaration:

// pre: c is a valid comparator
// post: sort this vector in the order determined by c
public void sort(Comparator<E> c)

Comparator is a Java interface, which, essentially, looks like:

public interface Comparator<E> {
    /*
     * Returns:  < 0  if a is smaller than b
     *             0  if a equals b
     *           > 0  if a is larger than b
     */
    int compare(E a, E b);
}

You will develop some classes that implement the Comparator interface. Comparator is parameterized by the type E of object that it compares. In the case of the sort method, the type of c is Comparator<E>—that is, c must implement a comparator for the type of data (E) stored in the vector. This sort method then uses the Comparator object c to perform comparisons of the values in MyVector. You may use any sorting algorithm you want in your sort implementation, although it may be best to start with a simple algorithm like selection sort. You can be more ambitious once the basic assignment is working.

When writing new comparators, you will specify what type they are defined for. For example, we would define a CardComparator class to compare Card objects as follows:

import java.util.Comparator;

public class CardComparator implements Comparator<Card> {
    ...
}

The compare method in that class would then take two Card objects as parameters.

Be sure to test MyVector thoroughly before going on to the next part. MyVector inherits a toString() method from Vector, which should be handy for printing out the contents of your vectors during testing.

Step 4: Reading the Phone Book

Now, write a program that reads Williams College phone data into a MyVector and answers some questions by sorting it with the appropriate Comparator applied. The file newphonebook.txt contains student entries, represented by three lines, and separated by a line of dashes:

Iluv C Science
Poker Flats B5
4135973427 3334 5406394821
-----------------
Jeannie Albrecht
Thompson Chemistry Lab 304
4135974251 1234 4134581234
-----------------
...

The first line is the name of the student, the second is their campus address, and the third contains the campus telephone number, SU box number, and home (or cell) phone number. You will need to create a Student class to represent all the information for a single student.

Once you have your Student class working, you will write code to read in the data file of student information and create a MyVector of Student objects. Your code should then perform whatever operations are necessary to answer the questions in step 5 below. [footnote: 2]

Note: you should read in phone numbers as long data (using the Scanner’s nextLong() method) rather than int data, because integer variables cannot store numbers much greater than 2 billion due to their internal representation.

Step 5: Answer Phone Book Questions

Your program should print out answers to the following questions. Include the answers to these questions in your PROBLEMS.md file.

  1. Which student appears first in a printed phone book if names are printed as they appear in the data file (i.e., first name first)?
  2. Which student has the smallest SU box number? The largest?
  3. Which student has the greatest number of vowels in their full name? You may ignore “y”s when counting vowels.

  4. Which address is shared by the most students, and what are their names? (Please list both the address, and the names of the students at that address.) You may find it useful to build a second vector that stores an Association between an address and the number of students living there. A special Comparator can then be used to sort that vector by comparing the number of students at each address. Once the most common address is known, you can consult the original vector of students to print out the people living at that address.

    Treat dorm rooms as unique addresses. For example, if two students shared a double in Morgan 13, they would have one address; however, those students would not share an address with any student living in Morgan 17.

    Note that some students have the address UNKNOWN because they are abroad, on leave, etc. These students should be ignored for this question. Other student entries with strange formatting should also be ignored (but please let your instructor know if you find any malformed entries).

  5. What are the ten most common area codes for student home phone numbers? Please print all ten area codes in decreasing order, along with the number of students who have a phone number with that area code. A phone number of -1 indicates that information is not available. For this question, you should disregard students without a known home phone number.

Optional: Simplifying Code with Lambda Expressions

As you are performing the above tasks, you may notice that writing them is fairly cumbersome. Writing a simple comparison method requires a great deal of notation to name the class, tell Java that it implements Comparator, create an object of that class, and so on.

With this in mind, Java 8 (and later versions of Java) have a much more concise way to specify a comparator: lambda expressions. To use a lambda expression, we simply pass in the method itself, rather than the entire comparator. In general, lambda expressions simplify notation in cases where we would otherwise need to create an object just to write a single method.

For example, let’s say we wanted to sort a vector storing objects of type Integer. Normally we would write a class called, say, CompareInteger that implements Comparator<Integer>. Its compare method would probably look something like:

public int compare(Integer i1, Integer i2) {
	return i1 - i2;
}

Then, to sort, we would write something like:

CompareInteger compInt = new CompareInteger();
sort(vec, compInt);

Using a lambda expression, you would not create any class type at all, nor would you create any object. Instead, you pass in the method you want to use directly, as follows:

sort(vec, (Integer i1, Integer i2) -> {
            int x = Integer.valueOf(i1);
            int y = Integer.valueOf(i2);
            return x - y;
          }
);

That’s a lot shorter! (And it works great.)

But in fact, it’s still redundant: Java knows that the type of i1 and i2 are Integer since they must always match the type of Vector. We can also take advantage of unboxing to just return i1 - i2 rather than casting to type int explicitly; the method could just return i1 - i2. Furthermore, if there’s only one line in the method being passed, it’s logical to assume it must be a return method, so that is also unnecessary, as are the curly braces and the final semicolon. Java allows us to skip all of this, allowing us to sort a vector of Integers with the following call:

sort(vec, (i1, i2) -> i1 - i2);

Pretty cool! You are free to use lambda expressions in your lab rather than creating new classes if you find that it is easier to work with.

One thing to be aware of: you still don’t want any lines of code to extend past 80 or so columns. If you sort calls wind up getting long, remember to put in line breaks so that they are still readable.

Lab Deliverables

By the start of lab, you should see a new private repository called lab05-sorting in your GitLab account.

For this lab, please submit the following:

cs136lab05_sorting-{USERNAMES}/
    README.md
    MyVector.java
    Student.java
    newphonebook.txt
    testphonebook.txt

Please also remember to submit the .java files for any additional comparator classes you write.

The MyVector.java and Student.java files contain starter code. Recall in the previous lab that you had a TestLinkedList.java file that contained a convenient main method pre-populated with a variety of helpful tests. It is always a good practice to create a small set of tests to facilitate development, and you are encouraged to do so here.

As with all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program appropriately: include pre/post conditions and assertions where appropriate. We will also be looking at how well you organize your code. Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods. Think carefully!

Submitting Your Lab

As you complete portions of this lab, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "We are the sole authors of the work in this repository." in the comments at the top of your Java files.

Lab notes:

[1] Avoid the statement import java.util.* for this assignment because java.util also provides a Vector class. This lab uses the Vector class from structure5. Instead, write import java.util.Comparator to import just Comparator.

[2] While you can write all of your code in the main method of your Student class, we consider this poor form. Instead, create a new class that will be responsible for reading in the data and performing each operation.

  • CSCI 136, Spring 2022

Website for CSCI 136, Spring 2022 (instructors: Sam McCauley and Dan Barowy)

Powered by Bootstrap 4 Github Pages