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.
- Create a new Eclipse project by copying ProjectTemplate.
Name the new project QueueSort.
- 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.
- 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.
- 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
- 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.
- In Queue1LSort1.java, complete the body of the removeMin
static method which you should have done as the homework.
- 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.
- 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
- Modify QueueSortMain so that it sorts the Strings
in decreasing lexicographic order:
- Create a new nested class in QueueSortMain.java
by copying and pasting StringLT, naming it StringGT;
- Edit the compare method in StringGT
so that it reverses the order of comparison;
- Update the main method so that this new
implementation of Comparator<String> is used;
- Run the program to test whether the program now sorts
in the reverse order from the original.