Lab: Queue Selection Sort

Objective

In this lab you will use the selection sort algorithm to implement the sort instance method for the Queue family of components and the removeMin static helper method.

Setup

Follow these steps to set up a project for this lab.

1. Create a new Eclipse project by copying ProjectTemplate. Name the new project QueueSort.
2. Open the src folder of this project and then open (default package). For this lab, you will need two files. As a starting point you can use any of the Java files. Rename one Queue1LSort1 and another one QueueSortMain and delete the other files from the project.
3. Follow the link to Queue1LSort1.java, select all the code on that page and copy it to the clipboard; then open the Queue1LSort1.java file in Eclipse and paste the code to replace the file contents. Save the file.
4. Follow the link to QueueSortMain.java, select all the code on that page and copy it to the clipboard; then open the QueueSortMain.java file in Eclipse and paste the code to replace the file contents. Save the file.

Method

1. First carefully look through the file QueueSortMain.java, which is a test driver for a Queue1LSort1 extension for Queue1L<String>, to get an idea of the overall structure and to see what the main method does. In particular, note the declaration of the StringLT nested class that provides an implementation for the Comparator<String> interface using the lexicographic order for Strings, and its use in the main method.
2. In Queue1LSort1.java, complete the body of the removeMin static method which you should have done as the homework.
3. Still in Queue1LSort1.java, complete the body of the sort instance method. Here the code is slightly different from what you wrote on the homework, because Queue1LSort1 here is an extension (of Queue1L<String>), sort is an instance (not static) method, and the queue being sorted is called this, not q.
4. Run the QueueSortMain test program. You can create your own input file with strings you'd like to sort, or save lines.txt to the data folder in your project and use it to test your code. Fix any problems you discover.

Additional Activities

1. Modify QueueSortMain so that it sorts the Strings in decreasing lexicographic order:
   1. Create a new nested class in QueueSortMain.java by copying and pasting StringLT, naming it StringGT;
   2. Edit the compare method in StringGT so that it reverses the order of comparison;
   3. Update the main method so that this new implementation of Comparator<String> is used;
   4. Run the program to test whether the program now sorts in the reverse order from the original.