Computer Science 210
Data Structures

Fall 2016, Siena College

Lab 5: Sorting with Comparators
Due: 10:00 AM, Wednesday, October 19, 2016

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.

Practice Program: Write a Java application in a program that takes any number of integers as command-line parameters (though they will come to you as String values) and prints their sum. (6 points)

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.

Question 1: Perform a brief study of the three sorting algorithms we discussed in class using this program. Generate a table of run times for each sorting algorithm for each input type (unsorted, sorted, reverse sorted) for a variety of array sizes. So you will have a total of 9 sets of numbers. A good choice of problem sizes might be to start at 500 and keep doubling until you start to get stack overflow errors. Do your timing results match the expected best case, average case, and worst case behavior of these algorithms? (10 points)

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:

Question 2: Answer Thought Question 1 on p. 147-148 of Bailey. (3 points)

Question 3: Answer Thought Question 2 on p. 148 of Bailey. (3 points)


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


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

> FeatureValueScore correctness 6
Timing Sorting Algorithms 10
MyVector correctness 12
MyVector test in main method 5
Comparators correctness 6
MyVector and Comparators design and style 5
MyVector and Comparators documentation 6
Sorting applications 4
Bailey Thought Question 1 3
Bailey Thought Question 2 3
Total 60