Lab 12: Smaller/Bigger Sort

Learning Outcomes

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:

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:

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.

Tips:
  • 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:

  1. Call smallerBigger() on the range.
  2. Store the returned pivot index.
  3. Recursively sort the range before the pivot.
  4. 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:

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:

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:

  1. a brief description of how you performed the benchmark;
  2. a table or chart summarizing your measurements;
  3. your conclusion about how starting order affects performance; and
  4. 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.

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

Development Checkpoints

The README contains the checklist for the required intermediate commits:

  1. Commit 1 — "JavaDoc"
  2. Commit 2 — "smallerBigger Tests"
  3. Commit 3 — "smallerBigger Implementation"
  4. Commit 4 — "Lab completed"

Push each checkpoint as required by the Canvas assignment.

Acknowledgement

This assignment was originally developed by Dr. Chris Taylor.