Kotlin
Java

Quicksort
Kotlin

Created By: Geoffrey Challen
/ Updated: 2021-11-13

Today 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!

Partitioning

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.

Provide an overview of Quicksort.

Like Mergesort, Quicksort is also based on another building block: partitioning. Let's see how that works:

Explain partitioning visually. Discuss how this can be used to create smaller problems to solve. This explanation should be language agnostic!

You'll get to complete partition on today's homework! But we can at least experiment with it using the method built-in to our playground:

Experiment with (but don't implement) partition. Demonstrate that the implementation uses the first value in the array.

Quicksort

Next, first we'll implement Quicksort. Then we'll analyze its performance!

Implementation

Next, let's build a recursive sorting algorithm based on Partitioner.partition! Once we have a partition method, completing the implementation is quite straightforward!

Complete the implementation of Quicksort based on the built-in partitioner.

Performance Analysis

Next, let's use the Quicksort implementation we completed above to experiment with its performance. Surprises are in store!

Experiment with the performance of Quicksort. Show both the average case behavior and the worst-case behavior.

What's going on here? Let's consider things visually.

Explain Quicksort visually using a diagram. Discuss both best- and worst-case performance. This explanation should be language agnostic!

Sorting Algorithm Review

Our next quiz will focus on sorting algorithms, and particularly the ones that we've covered together:

Let's review salient aspects of sorting performance. Specifically: best and worst case inputs and runtime, and memory usage.

Review sorting algorithms and their performance characteristics. This explanation should be language agnostic!

Sorting Tradeoffs

Sorting algorithms represent a fascinating set of tradeoffs between different performance attributes. For example:

  • Have a very small array to sort? Insertion sort can actually outperform other algorithms on small arrays, because the recursive calls needed by Mergesort and Quicksort have some overhead associated with them.
  • Want predictable performance? Mergesort has your back. O(n log n), O(n log n), O(n log n). Sometimes it's actually more important that a sort take a predictable amount of time than that it be completely optimal.
  • Short on space? Quicksort's space utilization is substantially smaller than Mergesort, and with good pivot selection it can achieve similar performance.

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.

Sorting Stability

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.

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough