# Lab 6: 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 | 3 | 8 | 5 | 12 | 1 | 8 | 18 | 13 |

becomes

0 | 1 | 2 | 3 | ☟ | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

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.

## Details

You will create a class, `SmallerBiggerSort`

with three class methods:

— 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>> int smallerBigger(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, int startInclusive, int endExclusive)`

— calls the recursive`public static <T extends Comparable<T>> void sort(List<T> list)`

`sort()`

method with the bounds of the list.

- 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: in 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.

Implement, `smallerBigger(List<T> list, int startInclusive, int endExclusive)`

, that
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 |

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 | 3 | 8 | 5 | 12 | 1 | 8 | 18 | 13 |

the `list`

becomes

➦ | 1 | 2 | 3 | ☟ | 5 | 6 | 7 | 8 | 🛑 |
---|---|---|---|---|---|---|---|---|---|

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:

➦ | 1 | 2 | 3 | 🛑 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |

producing

➦ | 1 | 2 | 3 | 🛑 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

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:

0 | ➦ | 2 | 3 | 🛑 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

1 | 3 | 8 | 5 | 8 | 8 | 12 | 18 | 13 |

which leads to `sort(list, 2, 4)`

and this result:

0 | 1 | ➦ | 3 | 🛑 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

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:

0 | 1 | 2 | 3 | 4 | ➦ | 6 | 7 | 8 | 🛑 |
---|---|---|---|---|---|---|---|---|---|

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:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|

1 | 3 | 5 | 8 | 8 | 8 | 12 | 13 | 18 |

- 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 of 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.

## 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?

## Acknowledgements

This assignment was originally developed by Dr. Chris Taylor.