We continue our discussion of sorting algorithms by introducing the wild child: Quicksort. Quicksort can achieve best-case sorting behavior while using less space than Mergesort. But, Quicksort also has some pathological cases we need to understand. Let’s get started!
You knew it was coming…
Create a public class named BinaryTreeValuesAtLevel
providing a single static method valuesAtLevel
.
valuesAtLevel
accepts a BinaryTree<Comparable>
(from cs125.trees
) and a level as an int
.
It should return, as a List<Comparable>
, all the values in the passed tree that are at the passed level, sorted
in ascending order.
If the passed tree is null
, or the level is negative, you should throw an IllegalArgumentException
.
The level corresponds to the depth of the node in the tree. So the root node is at level 0, its children are at level 1, its children's children are at level 2, etc.
To complete this question you probably need a helper method.
Our suggestion is that the main valuesAtLevel
create the list, begin the recursion, and sort the result.
(Just use a built-in sort.)
Your recursive method will need to track both the current level in the tree and the target level.
Once the target level is reached, the current node's value should be added and the recursion can stop.
You will also want to pass the list created by your main method.
Mergesort was our first recursive sorting algorithm. It employed a bottom-up approach—first breaking the array into individual chunks, and then merging them back together.
Quicksort is another recursive approach, but it works differently. Let’s first examine its operation at a high level, and then break it down further.
Like Mergesort, Quicksort is also based on another building block: partitioning. Let’s see how that works:
You’ll get to complete partition
on our next homework!
But we can at least experiment with it using the method built-in to our playground:
Next, first we’ll implement Quicksort. Then we’ll analyze its performance!
Next, let’s build a recursive sorting algorithm based on Partitioner.partition
!
Once we have a partition method, completing the implementation is quite straightforward!
Next, let’s use the Quicksort implementation we completed above to experiment with its performance. Surprises are in store!
What’s going on here? Let’s consider things visually.
Let’s review the sorting algorithms we’ve covered together:
Let’s review salient aspects of sorting performance. Specifically: best and worst case inputs and runtime, and memory usage.
Sorting algorithms represent a fascinating set of tradeoffs between different performance attributes. For example:
Timsort, the default sorting algorithm used by several languages including Python and Java, actually combines elements of both insertion sort and Mergesort, in addition to some other tricks.
As a final note, let’s discuss sort algorithm stability. Stability is a desirable property of sorting algorithms. It means that items with equal values will not change positions while the array is sorted.
Why is stability desirable? Because it allows us to run a sorting algorithm multiple times on complex data and produce meaningful results.
For example, imagine that want a list of restaurants sorted first by cuisine and then by name. Assuming our sorting algorithm is stable, we can accomplish this by first sorting the list by name and then by cuisine. However, if the sorting algorithm in unstable that second sort by cuisine will destroy the results of the sort by name, and render the combination meaningless.
Create a public, non-final class named Partitioner
. Implement a public static method
int partition(int[] values)
that returns the input array partitioned using the first
array value as the pivot. All values smaller than the pivot should precede it in the array,
and all values larger than or equal to the pivot should follow it. Your method should return the
index of the pivot value. If the array is null
or empty you should return -1.
Need more practice? Head over to the practice page.