Task 2: Sorting

Look at the SortingAlgorithm interface in the sorts package. Here it is, without its comments:

public interface SortingAlgorithm<T extends Comparable<T>> {
  void sort(List<T> list);
  String name();
}

Given a SortingAlgorithm, we can ask it to sort a List, and we can ask it for its name. The type parameter says that T must be Comparable: a sort has to be able to ask whether one element is less than another.

NullSort and GnomeSort are given. NullSort does nothing; it is a baseline for the reports. GnomeSort is a slow quadratic sort; read it to see how a sort is written against the List interface.

Implement the four other sorts. Each one must be the version the notes teach:

  • SelectionSort: each pass finds the largest element in the unsorted part and swaps it into the last position of that part. If the largest element is already there, it does not swap.
  • BubbleSort: the version with early termination. It stops after a pass that makes no swaps.
  • InsertionSort: the shift-based version. Larger elements shift one position to the right, and the key is written once, into its place.
  • MergeSort: the recursive version. Merge the two sorted halves into a temporary ArrayList, then copy the merged values back into the list with set.

Write every sort with only the get, set, and size operations of the list you are sorting. The counts in the reports then show the reads and writes each algorithm makes.

The starter declares the private helpers each sort must use, such as indexOfMax in SelectionSort, and merge and the recursive sort(list, start, end) in MergeSort. Read the comment above each one: it says what the helper does. The auto-test calls the helpers directly and checks each one on its own.

The tests in SortingAlgorithmTest check that each sort sorts. The auto-test also checks that each sort is the version described above. For example, it checks that bubble sort stops early on a sorted list, and that insertion sort shifts instead of swapping. It also checks that bubble sort, insertion sort, and merge sort are stable.