Week 12 Lab: Smaller/Bigger Sort

Learning Outcomes

Use the compareTo() method from the Comparable interface to determine which of two objects is bigger
Understand and apply recusion in algorithm development

Overview

In this assignment you will implement a recursive algorithm to sort elements of a list. The basic idea is to look at the first element in the list - let's call it first - and rearrange the list such that all of the elements smaller than first appear before first and all elements bigger than first appear after first. Elements equal to first can appear on either side of first. For example,

☟	1	2	3	4	5	6	7	8
8	5	8	3	12	1	8	18	13

becomes

0	1	2	☟	3	5	6	7	8
5	3	1	8	8	12	8	18	13

We now have a sublist of elements from index 0 to (but not including) index 4 with elements no bigger than 8 and a sublist of elements no smaller than 8 from index 5 to index 9. The elements in the sublists can be in any order.

Details

You will create a class, SmallerBiggerSort with four class methods:

public static <T extends Comparable<T>> int smallerBigger(List<T> list, int startInclusive, int endExclusive) — used to get a feel for how the non-recursive portion of the next method works. The method returns the index where the first element ended up being placed.
public static <T extends Comparable<T>> void sort(List<T> list, int startInclusive, int endExclusive) — a recursive sort method that works by creating sublists of all the elements smaller than a particular value and larger than the value (details below).
public static <T extends Comparable<T>> void sort(List<T> list) — calls the recursive sort() method with the bounds of the list.
public static <T> void reportStep(List<T> list, int startInclusive, int endExclusive, int sortedIndex) — prints the current state of the list after each step as a formatted console output.

Tips:

A significant portion of this assignment is related to your analysis (see end of assignment). Make sure you complete the coding part of this assignment well in advance so that you have time to give appropriate attention to the analysis.
Writing your tests before or as you implement your solution may help you understand the requirements of the code and design better solutions.
The Comparable interface requires the compareTo() method to be implemented. This method specifies how to compare two objects.

Note: The examples below are just examples, the order of the elements in the sublist does not need to match what is shown in these examples.

`smallerBigger()`

Implement, smallerBigger(List<T> list, int startInclusive, int endExclusive), such that it places all of the elements smaller than first = list.get(startInclusive) between position startInclusive and the location first and all elements larger than first between the location of first and position endExclusive. This method must be \( O(n) \) when an ArrayList is used. For example, smallerBigger(list, 2, 6); where list is:

0	1	➦	3	4	5	🛑	7	8
8	3	8	5	12	1	8	18	13

the list becomes

0	1	➦	3	4	5	🛑	7	8
8	3	1	5	8	12	8	18	13

Recursive `sort()`

Next implement sort(List<T> list, int startInclusive, int endExclusive) which sorts the list by recursively creating sublists of smaller and larger elements. For example calling sort(list, 0, 9) with list

➦	1	2	3	4	5	6	7	8	🛑
8	5	8	3	12	1	8	18	13

the list becomes

➦	1	2	☟	4	5	6	7	8	🛑
5	3	1	8	8	12	8	18	13

We now have two sublists that need to be sorted, so we need to call sort(list, 0, 3) and sort(list, 4, 9). sort(list, 0, 3) looks like:

➦	1	2	🛑	4	5	6	7	8
5	3	1	8	8	12	8	18	13

producing

➦	1	2	🛑	4	5	6	7	8
3	1	5	8	8	12	8	18	13

We now have just one sublist that needs to be processed: sort(list, 0, 2) to get:

➦	1	🛑	3	4	5	6	7	8
1	3	5	8	8	12	8	18	13

which leads to sort(list, 1, 2) which is a list with only one value, so nothing changes:

0	➦	🛑	3	4	5	6	7	8
1	3	5	8	8	12	8	18	13

Now the sort(list, 0, 3) call is complete and we can progress with the sort(list, 4, 9) call:

0	1	2	3	➦	5	6	7	8	🛑
1	3	5	8	8	12	8	18	13

resulting in no changes, but a recursive call to sort(list, 5, 9) swaps the 12 and 8 and produces this result:

0	1	2	3	4	➦	6	7	8	🛑
1	3	5	8	8	8	12	18	13

This gives us two recursive calls: sort(list, 5, 6) which produces a list of size 1, so no change occurs, and sort(list, 7, 9) which swaps the 18 and 13 producing a sort list:

0	1	2	3	4	5	6	7	8
1	3	5	8	8	8	12	13	18

`reportStep()`

After each step in the sorting algorithm (i.e. after each call to smallerBiggerSort) use this helper method to print to the console what was done. Specifically, what range was being worked on, what the value of the first element in the range is, the index that element ended up at after the sorting step was completed, and the current state of the list. The value should be highlighted red. Below is a sample of the expected output from the above example.

Sample Output

Tips:

There are several ways that you could implement smallerBigger() in O(n) time.
One simple way would be to make multiple passes through the list.
On the first pass, count how many elements are smaller than the first element. Once you know this, you can determine the final resting place for the first element.
Create a new list and put all the elements that are less than the first element in the beginning of the list, place the first element next, and then place all of the remaining elements into the list.

Testing

Write thorough JUnit tests for your implementation. Be sure to test each method separately on any boundary conditions you may encounter as well as typical (also referred to as "happy path") values. To make testing easier, make all the methods public. Also verify your console output matches the sample output.

Analysis

You must create a Word document that describes your approach, results of your benchmarking, and your analysis to answer the following question:

Does the performance of the algorithm change based on the starting order of the elements? For example, if the elements are sorted or nearly sorted, is it faster to sort than if the elements are in random order?

See your professor's instructions for details on submission guidelines and due dates.

Acknowledgement

This assignment was originally developed by Dr. Chris Taylor.