Lab 6: Smaller/Bigger Sort
Learning Outcomes
- Use the
compareTo()
method from theComparable
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<Comparable>
. 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
. For example,
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 8 | 3 | 8 | 5 | 12 | 1 | 8 | 18 | 13 |
becomes
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 8 | 5 | 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.
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.
Details
You will create a class, SmallerBiggerSort
with three class methods:
smallerBigger(List<Comparable> list, int start, int end)
— used to get a feel for how the non-recursive portion of the next method works.sort(List<Comparable> list, int start, int end)
— 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).sort(List<Comparable> list)
— calls the recursivesort()
method with the bounds of the list.
Implement a \( O(n) \) method, smallerBigger(List<Comparable> list, int start, int end)
, that
places all of the elements smaller than first = list.get(start)
between position start
and
the location first
and all elements larger than first
between the location of first
and position end
. For example, using start = 2
and end = 6
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 8 | 3 | 8 | 5 | 12 | 1 | 8 | 1 | 13 |
becomes
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 8 | 3 | 1 | 5 | 8 | 12 | 8 | 1 | 13 |
Next implement sort(List<Comparable>, int start, int end)
which sorts the
list by recursively creating sublists of smaller and larger elements. For example,
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 8 | 3 | 8 | 5 | 12 | 1 | 8 | 18 | 13 |
becomes
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |
We now have two sublists that need to be sorted, so we need to call sort(list, 0, 4)
and sort(list, 5, 9)
. sort(list, 0, 4)
looks like:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |
producing
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |
We now have just one sublist that needs to be processed: sort(list, 1, 4)
to get:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |
which leads to sort(list, 2, 4)
and this result:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 5 | 8 | 8 | 8 | 12 | 18 | 13 |
Now the sort(list, 0, 4)
call is complete and we can progress
with the sort(list, 5, 9)
call:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 5 | 8 | 8 | 8 | 12 | 18 | 13 |
resulting in no changes, but a recursive call to sort(list, 6, 9)
which, likewise causes no changes. The next recursive call is
sort(list, 7, 9)
which swaps the 18 and 13 producing a sort list:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
value | 1 | 3 | 5 | 8 | 8 | 8 | 12 | 13 | 18 |
Testing
Write thorough JUnit tests for your implementation.
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 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?
Acknowledgements
This assignment was originally developed by Dr. Chris Taylor.