Not every detail is spelled out for you in the problem descriptions. You will need to read the Java Documentation to fill in some of the details. You will need to be able to apply the various ways we managed abstraction, as discussed over several lectures.
You will have two main tasks in this assignment. The first is to create an
Algorithms class of sorting methods, described below. The second
is to provide an implementation of a Priority Queue (subject to the
restrictions outlined below) that extends the Java Collections Framework.
For the second task you should make a concerted effort to write as little
original code as possible, but still satisfy the restrictions given for the
design of the Priority Queue. Remember, the idea of the Java Collections
Framework is to provide you with a set of already-written (and tested!) methods
that you may use as is (or override if necessary).
Algorithms. Your Algorithms
class must provide the following methods:
Selection Sort works as follows:
When the program processes the list of data for the first time, it finds the location of the smallest item in the list. It then swaps the first item in the list with the smallest one (even if the smallest one is already in the first spot).
Next time around, it does the same, but only with the rest of the list, i.e. all items beyond the first one. The third time around, it starts with the third item, because the first two are already in the correct places, and so on.
This is hard to do with recursively constructed lists, but is much easier when we can directly swap two items at specific locations, as is the case when the data is stored in an ArrayList.
In the Algorithms class design a method called SelectionSort
that consumes an ArrayList<T> and an instance of a class that implements
Comparator<T> and mutates the ArrayList<T> so that it is sorted in the order given by the Comparator<T>.
It is possible to combine all parts of the Selection Sort algorithm into one method, but that is not a good way to design programs. Your program should use the following helper methods:
swap() that swaps the elements at the two given index positions in the given ArrayList<T>
findMinLoc() that finds in the given ArrayList<T> the
index of the minimum element among all elements, at the index greater than or equal to the given index. Of course, it also consumes the Comparator<T>.
We have seen a recursively-defined insertion sort algorithm. Here we design a version of insertion sort that works on an ArrayList, using loops.
First define a void method called insertIntoSortedList(). This method consumes an ArrayList<T> that is already sorted (according to the given Comparator<T>), an element of type T to insert into the ArrayList, and a Comparator<T>. The method inserts the new element into the ArrayList in the proper position, maintaining the list in sorted order. (You may use this method when implementing your Priority Queue, in Part 2).
Now use insertIntoSortedList() as a helper for the method insertionSort() that consumes an arbitrary (unsorted) ArrayList<T> and a Comparator<T> and produces a new sorted ArrayList<T>.
It accomplishes this by starting with an empty (sorted) list and inserting into it one by one all the elements of the given ArrayList Define a second version of insertion sort so that it mutates the existing ArrayList in place. Name your method insertionSortInPlace(). It consumes an arbitrary (unsorted) ArrayList<T> and a Comparator<T> and uses mutation
to sort the
given arraylist. Use helper methods (don't try to implement the entire
algorithm in one method).
Design a class called PriorityQueue<T>. Your PriorityQueue class must directly implement AbstractCollection<T>.
The underlying data structure for your Priority Queue should be an ArrayList<T> (i.e. the elements of the Priority Queue should be stored in
an ArrayList). The ArrayList should be maintained in sorted order so that
the item with the highest priority will always be the first (zeroth) item in
the ArrayList. The Priority Queue should provide the following methods:
/**
* retrieve and remove the item at the head of this priority queue
* (i.e. the item with the highest priority)
*
* @throws NoSuchElementException if the priority queue is empty
*/
T remove();
/**
* add the given element to this priority queue
*
* @param t the element to add
* @return true
*/
boolean add (T t);
/**
* retrieve, but do not remove, the item at the head of this priority queue
* (the item retrieved will be the item with the highest priority)
*
* @throws NoSuchElementException if the priority queue is empty
*/
T peek();
/**
* is this priority queue empty?
*
* @return true if this priority queue is empty
*/
boolean isEmpty();
Of course, the Priority Queue class must also provide implementations for all
of the obligations it inherits.
Provide in the Examples class tests that demonstrate
the functionality of your PriorityQueue class.
Create an archive of your Eclipse project (see "Saving your work" in Lab 4 if you forgot how to do this). Using web-based turnin, turn in a single zip file containing all code and documentation for this assignment. Follow the naming conventions when naming your file.