Assignment 9
Goals: Practice designing loops with ArrayList and Comparator. Learn some basic mutating sorting algorithms.
Instructions
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.
Make sure you follow the style guidelines for code indentation.
You will submit this assignment by the deadline using the Web-CAT submission system.
With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.
On top of every file you submit you will have the names of both partners, and the pair number.
The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.
Due Date: Friday, November 9th, 11:59 pm.
Practice Problems
Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.
Finish all of the problems from the Lab 9, except the last one.
Design in the Algorithms class the method countSuch that consumes a function object comp of the type ISelect<T> and counts the number of items in the given ArryaList<T> that satisfy the predicate defined by comp.
Problem 1
Finish and hand in the Selection Sort problem from the Lab 9.
Design a class Book (with the author and the title given as a String), and define five examples of books. Create two ArrayListss of books, one un-sorted by the author’s names, one un-sorted by their titles.
Design two classes that implement the Comparator<Book> interface, one that compares the books by their title, another that compares the books by the authors’ names. Use these two classes to design additional tests for your selectionSort method (two with each Comparator).
Problem 2
The Insertion Sort algorithm inserts each new item from the given collection of data into a list that is already sorted. You are familiar with the version of this algorithm implemented in the functional (immutable) style.
We can implement the same idea mutating in place the given ArrayList, making small changes until the whole ArrayList is sorted. (The selection sort you have just worked on is also an in-place algorithm.)
Assume that the ArrayList has a part at the low end alrady sorted, and the rest still needs to be sorted:
>.. sorted .......< >.. unsorted .....< |
+---+---+---+---+---+----+---+---+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 || 5 | 6 | 7 | 8 | 9 | |
+---+---+---+---+---+----+---+---+---+---+ |
value: | d | h | m | p | w || t | k | b | u | g | |
+---+---+---+---+---+----+---+---+---+---+ |
To do:
Design the method insert that will insert the next element of the given partially sorted ArrayList<T> into the sorted lower half. The method consumes the ArrayList<T>, the index of the first element in the unsorted part, (for the example above it would be $5$, and it traverses over the list down to the beginning, moving the out-of-order items to the right. The method also consumes the Comparator<T> that defines the ordering to be used in the insertion.
After the execution of this method the ArrayList would be:
>.. sorted ...........< >... unsorted..< |
+---+---+---+---+---+---+----+---+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 | 5 || 6 | 7 | 8 | 9 | |
+---+---+---+---+---+---+-=--+---+---+---+ |
value: | d | h | m | p | t | w || k | b | u | g | |
+---+---+---+---+---+---+----+---+---+---+ |
After another invocation of the insert methods it would be:
>.. sorted ...............< >.unsorted.< |
+---+---+---+---+---+---+---+----+---+---+ |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 || 7 | 8 | 9 | |
+---+---+---+---+---+---+-=-+----+---+---+ |
value: | d | h | k | m | p | t | w || b | u | g | |
+---+---+---+---+---+---+---+----+---+---+ |
The main loop of the insertion sort starts with the entire list being unsorted. It invokes the insert method with index $1$, then $2$, and so on, the last time with index list.size() - 1.
To do:
Design the method insertionSort that consumes an unsorted ArrayList<T> and a Comparator<T> and mutates the list into one sorted in the order defined by the given Comparator.
Note: The main loop method described above should be just a helper method for the insertionSort method.
Problem 3
Design the mehtod merge that consumes two sorted ArrayList<T>s and a Comparator<T> that defines their ordering and produces a new sorted ArrayList<T> that contains all items from both lists.