Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

This week's lab focuses on sorting. You will learn the power of Java's Comparator interface as it applies to writing a generalized sorting method. You will extend the functionality of an existing class using inheritance, you will implement a simple sorting procedure within this extension, and you will learn about Comparators, which provide a more flexible mechanism for ordering objects than the Comparables we have seen in class.

You may work alone or in a group of two or three on this lab. Of course, collaboration with your partner is unrestricted. You may discuss the lab with your classmates and give and receive some help, but your submission must be your own work (or that of you and your teammates, if you choose to form a group).

Getting Set Up

To get your BlueJ environment set up for this week's lab assignment, start BlueJ and choose "New Project" from the "Project" menu. Navigate to your folder for this course and choose the name "Lab5" (no spaces) for the project.

Create a document where you will record your answers to the lab questions. If you use plain text, call it "lab5.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab5.pdf" before you submit it.

The BlueJ Debugger

As our programs become more complex, the errors we introduce during coding can be more difficult to find. Sprinkling your program with System.out.println calls to see information about what is going on is a tried and true technique that works quite well in many cases. However, it is also very well worth being familiar with other tools, like visual debuggers. Our BlueJ IDE has a very nice debugger. If you are not already familiar with it, please watch Dr. Small's video tutorial.

There is nothing to submit for this part, but you will be expected to be able to use the debugger when asking for help with future programs.

Command-line Parameters

We can provide information to a Java application through the args parameter to its main method. As you can see from the main method signature we have been using all semester, it is an array of Strings. These String values come from what the program's user types after its name on the command line when running the program. Different Java IDEs provide different mechanisms for specifying these Strings, known as command-line parameters. In BlueJ, these are specified in a dialog box that we have been ignoring each time we run a Java application - the one that comes up after you choose main from the right-click menu to run your application. To specify the command-line parameters, we specify them as an array of String with the same syntax as a statically initialized array in Java. For example, we could specify an array of 3 String values:

  { "Java", "is", "fun" }

The Java run-time system will construct and initialize an array with these values, and we can access "Java" as args[0], "is" as args[1], and "fun" as args[2] in our program's main method.

Note: you can convert a String whose contents can be interpreted as an integer value to an int by passing it to the Integer.parseInt method.

Timing Sorting Algorithms

The SortingComparisons example allows you to run a suite of sorting algorithms on arrays of a size specified in a command-line parameter.

Programming Assignment

We will do the laboratory at the end of Chapter 6 in Bailey. You will need to read about the Comparator interface in Section 6.8.

Please note the following clarifications, modifications, and explanations relating to the lab procedure outlined in the text:

• In step 1, you are asked to create an extension of structure.Vector called MyVector. Since we are using the generic version of the structure package, you will extend structure5.Vector. Your class header for MyVector should look like this:

  public class MyVector<T> extends structure5.Vector<T>
  

  We have not yet discussed inheritance, which is what allows one class to extend another, but you don't need to know too much about it to do this. Basically, your MyVector class will be able to do everything a structure5.Vector, plus anything you add in your MyVector class definition. In particular, your extension of structure5.Vector, methods of MyVector will have access to instance variables and methods declared as protected in the structure5.Vector implementation. Make good use of this fact!

  Important Note: The elementData array in structure5.Vector is declared as private rather than protected for type safety reasons. This means, unfortunately, that MyVector will not be able to access the array directly. Fortunately, Vector has mutator and accessor methods that are (almost) as good as direct access to the array.

  Another Important Note: You do not need to copy or rewrite Vector.java! When you extend the existing Vector code, it will inherit all of the constructors and methods. You're just adding one method.

• In step 2 of the lab procedure in Bailey, you are to write a sort method. The structure of the code will be very similar to what you have seen in our class and text examples, but you will need to modify it to use Comparators (as opposed to primitive types or Comparable objects) and to operate on the internal array of your instance of MyVector (as opposed to an array or other structure you would pass in as a parameter).
• Be sure to test your sort method in MyVector thoroughly before going on to step 3 of the lab assignment procedure. A good way to do this is to create a MyVector of some Comparable class (like Integer or String) and use structure5.NaturalComparator for your Comparator. Include this test as part of your submission as a main method of your MyVector class.
• For part 3 of the lab procedure, write two applications (three if you are working in a group of three). They should each work on a different data file and each should perform more than one "interesting" sort process. Both/all three will use the same MyVector class, but each application will call its own class for encapsulating the data objects you are working with, and a number of Comparators to sort the data in different ways. You should have a total of at least five (seven, if working in a group of three) unique Comparators in your submission.

  You may choose from the data files I have provided by email (see the README file there for more information) or you may use some other data that you find interesting. Please include all data files that you use in your submission.

  Whatever types of data you choose to use, you will need to implement a custom class that holds the details of each type of data, Comparators that can compare instances of that class by different criteria, and an Java application that uses those Comparators to sort a MyVector that holds instances of your custom class in multiple ways. The file you have been emailed includes a data file movies.dat, whose entries are used to create instances of the provided MovieInfo class, three classes that implement Comparator and compare MovieInfo objects by different criteria, and an application MovieInfoSorter that uses a MyVector with the Comparators to sort the data in multiple ways. Please do not start implementing your own code for custom classes and comparators until you fully understand the ones provided!

Submitting

Before 10:00 AM, Wednesday, October 19, 2016, submit your lab for grading. There are two things to do to complete the submission: (i) Copy your file with the answers to the lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. and (ii) upload a copy of your lab (a .7z or .zip file containing your project directory) to Blackboard under "Lab5". Don't forget to check your programming assignment programs for compliance with the Style Guide for CSIS 210 Programs

Grading

This assignment is worth 60 points, which are distributed as follows: