Lab 6: Smaller/Bigger Sort

Learning Outcomes

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,

index012345678
value838512181813

becomes

index012345678
value138581281813

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:

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

index012345678
value83851218113

becomes

index012345678
value83158128113

Next implement sort(List<Comparable>, int start, int end) which sorts the list by recursively creating sublists of smaller and larger elements. For example,

index012345678
value838512181813

becomes

index012345678
value138588121813

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:

index012345678
value138588121813

producing

index012345678
value138588121813

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

index012345678
value138588121813

which leads to sort(list, 2, 4) and this result:

index012345678
value135888121813

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

index012345678
value135888121813

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:

index012345678
value135888121318

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?

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

Acknowledgements

This assignment was originally developed by Dr. Chris Taylor.