COMP 139 - Lab 5 - Collections and Sorting

Learning Outcomes and Introduction

In this lab assignment you will practice using lists and comparisons in the Java Collections Framework, in particular working with:

• java.util.List
• java.util.Collections
• java.util.Comparator
• java.util.Arrays

You will also write your own sorting method, and review what you've learned about:

• complexity analysis (Big-O)
• generics
• static methods
• lists and arrays

This assignment makes use of classes that you created in Lab 1 and Lab 2. However, to make that sure your solution will run when it is marked and to avoid problems related to incomplete or incorrect old code, we recommend that you use the solution classes provided in LabTests.jar (eg. ca.camosun.comp139.solution.lab3.Rational).

Task 1: Built-in Sorting and Comparators

Write a program that uses the collections framework to solve each of the following problems.

1. Given a list of Rational objects, find the smallest valued element.
2. Given a list of String values, find the one that is last in lexicographic order.
3. Given an array of Double values, find the maximum.
4. Given a list of Person objects, sort them by surname in lexicographic order.
5. Given a list of Employee objects, sort them by their salaries (lowest first), and then sort groups of employees with the same salary by surname in lexicographic order.
6. bonus Given a list of Employee objects, find the one with the highest salary. In case of a tie, return the one whose surname comes first in lexicographic order.
7. bonus Given a list of Patient objects, find a patient that does not have an assigned physician (ie. physician is null). If there is more than one, return the one whose surname comes first in lexicographic order.

Write your solution for each problem as a separate single-argument static method. Call these from your main method with some example data to prove that they work properly. Your solutions should work for any valid input list or array, but your main method only needs to show one example of each.

To solve these problems, you will likely need to use:

• Arrays#asList(T...)
• Collection#addAll(Collection)
• Collection#removeIf(Predicate)
• Collections#max(Collection)
• Collections#max(Collection, Comparator)
• Collections#min(Collection)
• Collections#min(Collection, Comparator)
• Comparator#comparing(Function)
• Comparator#comparingInt(ToIntFunction)
• Comparator#naturalOrder()
• Comparator#reverseOrder()
• Comparator#thenComparing(Function)
• Comparator#thenComparing(Function, Comparator)
• List#sort(Comparator) (or Collections#sort(List, Comparator))

Task 2: Custom Sorting Algorithm

The built-in sorting methods in Java are robust and sufficient for most tasks. However, they use algorithms that are very generalized and may not perform as well as code that is customized for a particular application. If speed is essential or available memory is limited, you may want to write your own sorting routines.

1. Write a custom sorting method that rearranges a List of Patient objects so that all the patients that do not have an assigned physician are moved to the front of the list, in ascending order by ID. The order of the remainder of the list (where patients have a non-null physician) is irrelevant.

   Your solution should have a method header that looks like:

   
   					public static <T extends Patient> void customSort(List<T> patients);
   				

2. In your main method, give an example where the sorting algorithm you created in step 1 is faster than a solution using Collections#sort(List, Comparator), and an example where it is slower.

Submission

Completing all tasks in this lab should result in a single main program (with as many supporting classes as needed) within a single package named like LastnameFirstname_lab5. Compress the package directory into a ZIP archive and upload it to the D2L assignment.

The marks for this lab are heavily weighted towards good coding practice and style. Pay attention to your code formatting, make sure you have documented all public members using JavaDoc, and make sure you are using constants, arrays, loops, and methods effectively.

NOTE: This assignment is to be done individually. You can help one another with problems and questions, but in the end everyone must do their own work.