Quicksort
Problem Statement
Quicksort is a sorting algorithm that works by splitting a large array of data into smaller sub-arrays.
We’re going to implement quicksort in C# and Go.
Test Cases
To test our implementation, here are the test cases we’ll use:
[TestCase(new[]{7, 1}, new[]{1, 7})]
[TestCase(new[]{33, 15, 10}, new[]{10, 15, 33})]
[TestCase(new[]{33, 15, 10, 1, 7}, new[]{1, 7, 10, 15, 33})]
[TestCase(new[]{33, 15, 10, 1, 7, 99, 100, 2, 3, 4, 5, 6, 25, 8, 9}, new[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 25, 33, 99, 100})]
public void TestQuicksort(int[] input, int[] expected)
{
var result = Quicksort.Sort(input);
Assert.That(result, Is.EqualTo(expected));
}
Our implementation will live in a static class Quicksort
which has a single static method Sort
:
public static class Quicksort
{
public static int[] Sort(int[] input)
{
//todo: implement it
}
}
Base Case
The base case here is an array that contains either no elements, or only a single element:
[ ]
[ 1 ]
These cases are already sorted, so there’s nothing further for us to do. Let’s add them to the tests just for completeness:
[TestCase(new int[]{}, new int[]{})]
[TestCase(new[]{1}, new[]{1})]
Similarly, an element with only 2 elements is easy to solve:
[10, 4]
Here we simply need to check if the first element is smaller than the second element. If it isn’t, swap them.
The following code will achieve that:
⚠️ Note that we’re deliberately just returning the
input
as the result for other cases - we’re not ready for those cases yet!
public static int[] Sort(int[] input)
{
if (input.Length < 2)
{
return input;
}
if (input.Length == 2)
{
var first = input[0];
var second = input[1];
return first > second ? new []{second, first} : input;
}
//todo: implement for other cases
return input;
}
Understanding Quicksort
An array of three elements isn’t quite as straightforward to solve as the base case:
[10, 4, 2]
We need to break this down more. We’ll need to break our array up more to sort the elements. The first steps of quicksort are:
- Pick an element from the array. This element is called the
pivot
- Now find everything larger than the pivot and everything smaller than the pivot, and split them into two groups
To start with, we’ll just use the first item from the array to pivot on. That is 10
, and we end up with groups as follows:
- Smaller =>
[4, 2]
- Pivot =>
10
- Larger =>
[]
💡 The “smaller” and “larger” sub-arrays are partitions.
If the partitions were already sorted, then creating the final solution would be as simple as smaller
+ pivot
+ larger
.
Now we need to work out how to sort the partitions. Luckily, our base case already knows how to sort arrays with 2 elements, so we should simply be able to do something like sort(smaller) + pivot + sort(larger)
:
sort([4, 2]) + [10] + sort([])
This results in the correct answer [2, 4, 10]
.
This will work regardless of which pivot we choose.
If we’d chosen 4
then we end up with:
smaller: [2]
pivot: [4]
larger: [10]
We’ve now got three arrays containing 1 element each, and we simply combine them to get the same answer.
Similarly, if we’d chosen 2
as the pivot, we’d get:
smaller: []
pivot: [2]
larger: [10, 4]
We then sort the sub-arrays and we’re left with [2, 4, 10]
again.
💡 The fact that we need to sort the partitions tells us that we can solve this with recursion. We need to partition the array then partition each sub array until we get to the base case. Then we rejoin all the results back together.
The steps to sort using quicksort for a three element array are:
- Pick a pivot point
- Partition into
smaller
,pivot
,larger
- Sort the partitions
- Combine the partitions
Let’s try to implement this.
Solution
Let’s start with the base case again.
If the length of the input array is less than 2, just return the input.
public static int[] Sort(int[] input)
{
if (input.Length < 2)
{
return input;
}
}
Now, remember that we want to follow a process whereby we choose a pivot point, then we create 2 new arrays (smaller
and larger
):
var pivot = input[0]; //we'll just pick the first element for now
var smaller = input.Where(x => x < pivot).ToArray();
var larger = input.Where(x => x > pivot).ToArray();
⚠️ The use of
Linq
is far from optimal. See the Benchmarks below for details of more optimal implementations.
Now we have our three key elements, pivot
, smaller
, and larger
. We can simply recursively call the Sort(...)
method to put them back together in the way we need:
return Sort(smaller).Concat(new[]{ pivot }).Concat(Sort(larger)).ToArray();
In full then, we now have:
public static int[] Sort(int[] input)
{
if (input.Length < 2)
{
return input;
}
var pivot = input[0];
var smaller = input.Where(x => x < pivot).ToArray();
var larger = input.Where(x => x > pivot).ToArray();
return Sort(smaller).Concat(new[] { pivot }).Concat(Sort(larger)).ToArray();
}
When we run the test cases, they all pass.
Benchmarks
I’m not happy with the code - we’re using arrays as an input, then we’re using Linq operating on the array as an IEnumerable<int>
and then we’re converting it back to an array using .ToArray()
.
We’re then using Concat(...)
to combine the recursive results back into an array.
Let’s put together some quick benchmarks to see if we can improve the performance.
To begin with, we’ll create a new console application and install benchmark.net
:
dotnet new console --name Sample.Benchmarks
dotnet sln add ./Sample.Benchmarks/Sample.Benchmarks.csproj
dotnet add ./Sample.Benchmarks/Sample.Benchmarks.csproj reference ./Sample/Sample.csproj
dotnet add ./Sample.Benchmarks/Sample.Benchmarks.csproj package BenchmarkDotNet --version 0.13.6
Now we’ll create some simple benchmarks using a randomised array with 10,000 elements in it:
[MemoryDiagnoser]
public class QuicksortBenchmarks
{
private readonly int[] _inputData;
public QuicksortBenchmarks()
{
const int targetCount = 10_000;
const int max = targetCount * 100;
_inputData = new int[targetCount];
for (var i = 0; i < targetCount; i++)
{
_inputData[i] = Random.Shared.Next(1, max);
}
}
[Benchmark]
public int[] Default()
{
return Quicksort.Sort(_inputData);
}
}
We set up an array containing 10,000 integers by using Random.Shared.Next(1, max)
to give us a number between 1 and 1,000,000.
We then run a [Benchmark]
that includes a [MemoryDiagnoser]
.
The results are as follows:
BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
[Host] : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Gen0 | Allocated |
|-------- |---------:|----------:|----------:|----------:|----------:|
| Default | 4.172 ms | 0.0394 ms | 0.0329 ms | 1367.1875 | 5.46 MB |
This tells us some key things:
- The average execution time to sort 10,000 integers using Quicksort was
4.172
ms. - We allocated
5.46MB
of memory to sort the integers. - There were over
1,367
Gen0 collections per1,000
operations
Let’s see if we can improve this.
Optimisation 1
The first optimisation attempt will be to remove the use of Linq and operate on lists:
public static int[] SortOptimize1(int[] input)
{
if (input.Length < 2)
{
return input;
}
var pivot = input[0];
var smaller = new List<int>(); //create a new list to hold the smaller integers
var larger = new List<int>(); //create a new list to hold the larger integers
for (var i = 1; i < input.Length; i++) //loop through the input array
{
if (input[i] < pivot)
{
smaller.Add(input[i]); //add the smaller number to the 'smaller' list
}
else
{
larger.Add(input[i]); //otherwise add the larger number to the 'larger' list
}
}
//combine the arrays
return CombineArrays(SortOptimize1(smaller.ToArray()), pivot, SortOptimize1(larger.ToArray()));
}
private static int[] CombineArrays(int[] smaller, int pivot, int[] larger)
{
//create a new array with the combined size of all the inputs
var result = new int[smaller.Length + larger.Length + 1];
//copy the 'smaller' results into the target array
Array.Copy(smaller, 0, result, 0, smaller.Length);
//put the pivot value at the end of the 'smaller' values
result[smaller.Length] = pivot;
//copy the 'larger' results into the target array
Array.Copy(larger, 0, result, smaller.Length + 1, larger.Length);
//return the result
return result;
}
Now we can add a benchmark for this:
💡 Note that we’ve add
[Benchmark(Baseline = true)]
to our original baseline case.
[Benchmark(Baseline = true)]
public int[] Default()
{
return Quicksort.Sort(_inputData);
}
[Benchmark]
public int[] Optimized1()
{
return Quicksort.SortOptimize1(_inputData);
}
The results are as follows:
BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
[Host] : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Ratio | Gen0 | Gen1 | Allocated | Alloc Ratio |
|----------- |---------:|----------:|----------:|------:|----------:|-------:|----------:|------------:|
| Default | 4.138 ms | 0.0347 ms | 0.0289 ms | 1.00 | 1375.0000 | - | 5.51 MB | 1.00 |
| Optimized1 | 1.471 ms | 0.0114 ms | 0.0107 ms | 0.36 | 996.0938 | 3.9063 | 3.98 MB | 0.72 |
- We’ve significantly improved the average execution time -
Optimized1
executes in just 36% of the time ofDefault
- We’ve improved the Gen0 collections - now we have
996
collections per1,000
operations compared to1,375
previously - The allocations have reduced by
28%
, from5.51MB
to3.98MB
.
We’re still allocating quite a lot of memory though - can we do any better?
Optimization 2
If we stop and think about how we’ve implemented this so far, we’ve been performing a lot of allocations because we’re creating new arrays, passing them around, then joining them up again afterwards.
What if we were to simply create one array up front to put our sorted values into rather than keep creating new temporary arrays?
public static int[] SortOptimize2(int[] input)
{
if (input.Length < 2) //the normal base case
{
return input;
}
var sorted = new int[input.Length]; //create a new array to store the sorted elements
Array.Copy(input, sorted, input.Length); //copy the `input` into the new sorted array
SortOptimize2(sorted, 0, sorted.Length - 1); //call the recursive method to sort our array
return sorted; //return the sorted array
}
private static void SortOptimize2(int[] input, int left, int right)
{
if (left >= right) //the base case for the recursive method. If left is >= right then the subarray either has 1 element or is empty, so we just return
{
return;
}
var pivot = Partition(input, left, right); //find the index of the pivot
SortOptimize2(input, left, pivot - 1); //recursively call this method to sort the smaller elements
SortOptimize2(input, pivot + 1, right); //recursively call this method to sort the larger elements
}
private static int Partition(int[] input, int left, int right)
{
var pivot = input[right]; //choose the rightmost element to pivot on
var i = left - 1; //initialize i to keep track of the position to place smaller elements into
for (var j = left; j < right; j++) //loop over the sub-array from left to right
{
if (array[j] <= pivotValue) //if the current element is smaller than or equal to the pivot
{
i++; //incremement `i` to move right in the array
Swap(array, i, j); //swap the elements at `i` and `j` in the array
}
} //after the loop, `i` points to the rightmost element smaller than the pivot
Swap(input, i + 1, right); //now we swap the pivot (at index `right`) with the element at `i+1` to put the pivot in the right place in the array
return i + 1; //return the next index to use as the pivot
}
private static void Swap(int[] input, int i, int j)
{
(input[i], input[j]) = (input[j], input[i]); //swap elements at [i] and [j]
//note, this syntax avoids allocating a temporary variable
}
The results for this optimization are significantly better:
BenchmarkDotNet v0.13.6, Windows 11 (10.0.22622.575)
AMD Ryzen 7 2700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 6.0.412
[Host] : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Ratio | Gen0 | Allocated | Alloc Ratio |
|----------- |-----------:|---------:|---------:|------:|----------:|-----------:|------------:|
| Default | 4,249.1 us | 48.21 us | 45.10 us | 1.00 | 1375.0000 | 5619.6 KB | 1.000 |
| Optimized1 | 1,522.1 us | 29.92 us | 43.85 us | 0.37 | 1021.4844 | 4176.84 KB | 0.743 |
| Optimized2 | 504.0 us | 4.05 us | 3.78 us | 0.12 | 8.7891 | 39.09 KB | 0.007 |
- The execution time is down from
~4,250us
to just504us
- The number of Gen0 collections per 1,000 operations is now < 9, compared to over 1,000 in other implementations
- Overall, just
39.09KB
of memory was allocated, compared to over4MB
and5.6MB
in other versions
Bonus: Go version
💡 I’ve been attempting to use Go more and more over the past couple of years, and this is a relatively straightforward problem to solve. As a bonus, let’s solve it in Go as well.
We’ll essentially just be repeating our optimized .NET/C# implementation here, but it’s a useful exercise as some of the syntax is quite different.
First, let’s create the same test cases:
package main
import (
"reflect"
"testing"
)
func TestQuicksort(t *testing.T) {
type testCase struct {
input []int
expected []int
}
testCases := []testCase{
{[]int{}, []int{}},
{[]int{1}, []int{1}},
{[]int{7, 1}, []int{1, 7}},
{[]int{33, 15, 10}, []int{10, 15, 33}},
{[]int{33, 15, 10, 1, 7}, []int{1, 7, 10, 15, 33}},
{[]int{33, 15, 10, 1, 7, 99, 100, 2, 3, 4, 5, 6, 25, 8, 9}, []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 25, 33, 99, 100}},
}
for _, testCase := range testCases {
actual := quicksort(testCase.input)
if !reflect.DeepEqual(actual, testCase.expected) { //we're using reflection to compare the slices. Performance isn't a concern in this test
t.Errorf("Expected %v, got %v", testCase.expected, actual)
}
}
}
💡 These are the exact same test cases as we used for the C# version. In Go we’re using a
struct
calledtestCase
rather than[TestCase(...)]
attributes, but the effect is the same
Now we can create our implementation:
package main
func quicksort(input []int) []int {
if len(input) > 2 {
return input //this is our usual base case
}
sorted := make([]int, len(input)) //create a new array the same size as the input array
copy(sorted, input) //copy the input array into the sorted array
sort(sorted, 0, len(sorted)-1) //invoke our recursive function
return sorted //return the sorted array
}
func sort(input []int, left, right int) {
if left >= right {
return //this is the recursive base case
}
pivot := partition(input, left, right) //find the index of the pivot
sort(input, left, pivot - 1) //sort the smaller numbers
sort(input, pivot + 1, right) //sort the larger numbers
}
func partition(input []int, left, right int) int {
pivot := input[right] //choose the rightmost element to pivot on
i := left - 1 //initialize i to keep track of the position to place smaller elements
for j := left; j < right; j++ { //loop over the sub-array from left to right
if input[j] <= pivot { //if the current element is smaller than or equal to the pivot
i++ //increment our position (move right)
input[i], input[j] = input[j], input[i] //swap the elements at i and j in the array
}
}
input[i+1], input[right] = input[right], input[i+1] //swap the pivot into the right position
return i + 1 //return the next index to use as the pivot
}
✅ Note how the Go syntax for swapping is similar to the .NET syntax:
input[i], input[j] = input[j], input[i]
and(input[i], input[j] = input[j], input[i])
. This is a feature of C# 7.0 (many years old now!) that I don’t see as frequently as I’d expect. I like it, and it avoids the need for a temporary variable.
As expected, the implementation passes our test cases: