Lab 12: Smaller/Bigger Sort
Learning Outcomes
- Use the
compareTo()method from theComparableinterface to compare objects. - Apply recursion to a divide-and-conquer sorting algorithm.
- Design meaningful tests for a method before implementing it.
- Compare algorithm performance using controlled benchmark inputs.
Overview
In this assignment you will implement a recursive algorithm to sort the elements
of a List.
The algorithm repeatedly chooses the first element of a range as a pivot. A partitioning step rearranges that range so that:
- every element smaller than the pivot appears before the pivot;
- every element larger than the pivot appears after the pivot; and
- elements equal to the pivot may appear on either side.
The relative order of elements within either partition is not required to be preserved.
For example,
| ☟ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---|---|---|---|---|---|---|---|---|---| | 8 | 5 | 8 | 3 | 12 | 1 | 8 | 18 | 13 |
could become
| 0 | 1 | 2 | ☟ | 3 | 5 | 6 | 7 | 8 | |---|---|---|---|---|---|---|---|---|---| | 5 | 3 | 1 | 8 | 8 | 12 | 8 | 18 | 13 |
The pivot is now in a position where every element before it is no greater than the pivot and every element after it is no less than the pivot. The two ranges on either side can then be sorted recursively.
Required Class and Methods
Create a class named SmallerBiggerSort containing these three public static
methods:
public static <T extends Comparable<T>> int smallerBigger(
List<T> list, int startInclusive, int endExclusive)
public static <T extends Comparable<T>> void sort(
List<T> list, int startInclusive, int endExclusive)
public static <T extends Comparable<T>> void sort(List<T> list)
All ranges use the standard Java convention:
[startInclusive, endExclusive)
The element at startInclusive is included in the range. The element at
endExclusive is not.
Do not use List.sort(), Collections.sort(), arrays sorting methods, or any
other library sorting method to implement this assignment.
smallerBigger()
Implement:
public static <T extends Comparable<T>> int smallerBigger(
List<T> list, int startInclusive, int endExclusive)
The first element in the range is the pivot:
T pivot = list.get(startInclusive);
Rearrange only the specified range so that:
- values smaller than the pivot are before it;
- values larger than the pivot are after it;
- values equal to the pivot may appear on either side; and
- elements outside the specified range are unchanged.
Return the index where the original pivot is placed.
The exact ordering of the smaller and larger groups is not important. Your implementation does not need to be stable.
This method must run in O(n) time for an ArrayList, where n is the
number of elements in the specified range.
For example, calling:
smallerBigger(list, 2, 6);
on:
| 0 | 1 | ➦ | 3 | 4 | 5 | 🛑 | 7 | 8 | |---|---|---|---|---|---|---|---|---|---| | 8 | 3 | 8 | 5 | 12 | 1 | 8 | 18 | 13 |
could produce:
| 0 | 1 | ➦ | 3 | 4 | 5 | 🛑 | 7 | 8 | |---|---|---|---|---|---|---|---|---|---| | 8 | 3 | 1 | 5 | 8 | 12 | 8 | 18 | 13 |
Other partition orders are also correct if they satisfy the requirements above.
Valid ranges
smallerBigger() requires a non-empty valid range:
0 <= startInclusive < endExclusive <= list.size()
Throw an IllegalArgumentException if the range is invalid.
A null list must result in a NullPointerException.
- There are several ways to implement
smallerBigger()in O(n) time. - One straightforward approach is to place elements smaller than the pivot into one temporary list and the remaining elements into another.
- Another approach may use multiple linear passes through the range.
- Whichever approach you choose, do not sort either partition with a library sorting method.
Recursive sort()
Implement:
public static <T extends Comparable<T>> void sort(
List<T> list, int startInclusive, int endExclusive)
This method must recursively sort only the specified range.
For a range containing fewer than two elements, there is nothing to do.
Otherwise:
- Call
smallerBigger()on the range. - Store the returned pivot index.
- Recursively sort the range before the pivot.
- Recursively sort the range after the pivot.
For example, after partitioning:
| ➦ | 1 | 2 | ☟ | 4 | 5 | 6 | 7 | 8 | 🛑 | |---|---|---|---|---|---|---|---|---|---|---| | 5 | 3 | 1 | 8 | 8 | 12 | 8 | 18 | 13 |
the recursive calls are:
sort(list, 0, 3);
sort(list, 4, 9);
Continue until every recursive range contains zero or one element.
Valid ranges
sort(list, startInclusive, endExclusive) accepts empty and single-element
ranges, but the indexes must satisfy:
0 <= startInclusive <= endExclusive <= list.size()
Throw an IllegalArgumentException if the indexes are outside those bounds.
A null list must result in a NullPointerException.
Initial sort()
Implement:
public static <T extends Comparable<T>> void sort(List<T> list)
This method sorts the entire list by calling the recursive sort() method with
the correct bounds.
A null list must result in a NullPointerException.
Your final implementation should not print debugging or recursion-tracing output. You may print temporary diagnostics while developing the algorithm, but remove them before benchmarking and before the final commit.
Testing
Write thorough JUnit tests for your implementation.
Your tests should include meaningful normal, boundary, and special cases. In particular, consider:
- the pivot being the smallest value;
- the pivot being the largest value;
- duplicate values;
- a subrange that does not include the entire list;
- a single-element range;
- empty and single-element lists for
sort(); - invalid ranges.
Your tests should verify the partition requirements, not one particular ordering of elements within the smaller or larger groups.
Analysis
Create a Word document describing your implementation, benchmark results, and analysis.
Investigate this question:
Does the performance of the algorithm change based on the starting order of the elements?
At minimum, compare lists containing the same number of values in these three starting arrangements:
- already sorted;
- reverse sorted;
- random order.
Use the same list size when comparing the three arrangements. Run each case multiple times rather than drawing a conclusion from one measurement. Do not include list construction, file I/O, console output, or other unrelated work in the timed portion.
Include:
- a brief description of how you performed the benchmark;
- a table or chart summarizing your measurements;
- your conclusion about how starting order affects performance; and
- an explanation of why the recursive algorithm behaves that way.
You do not need to determine a mathematically exact running-time formula, but your explanation should connect the observed behavior to where the first element is placed during each partition.
Development Checkpoints
The README contains the checklist for the required intermediate commits:
- Commit 1 — "JavaDoc"
- Commit 2 — "smallerBigger Tests"
- Commit 3 — "smallerBigger Implementation"
- Commit 4 — "Lab completed"
Push each checkpoint as required by the Canvas assignment.
Acknowledgement
This assignment was originally developed by Dr. Chris Taylor.