Overview
I recently started reading through Grokking Algorithms as a primer before starting to review more DS&A, and chapter 4 is about quicksort, which recursively uses a divide-and-conquer method to sort an array in ascending order.
The pictures in the book (one linked below) are really great at describing the call stack, and it got me thinking about easy ways to accomplish viewing how deep the call stack goes recursively when calling these functions.
Basics
The idea around quicksort is that you pick a pivot and then split the arrays into smaller and larger numbers from there. Depending on where you pick your pivot, it has an effect on the overall speed of your algorithm.
In the above example, this essentially shows the worst case. The algorithm is already sorted, and it just traverses over the entire array every time. This would be the equivalent to O(n^2). Anyway, that isn’t too important, and I more wanted to just document how you could use a closure in go to document this.
Zero index pivot
In go, it’s pretty common to utilize anonymous functions, and this Go By Example snippet has a good example of doing that here.
Now let’s take a look at an example of passing in a variable defined before the anonymous function to keep track of this when the array is already sorted:
zeroPivotMaxDepth := 1
var zeroPivot func([]int, int) []int
zeroPivot = func(nums []int, depth int) []int {
if depth > zeroPivotMaxDepth {
zeroPivotMaxDepth = depth
}
if len(nums) < 2 {
return nums
}
pivot := nums[0]
less := []int{}
greater := []int{}
for _, v := range nums[1:] {
if v <= pivot {
less = append(less, v)
} else {
greater = append(greater, v)
}
}
sorted := zeroPivot(less, depth+1)
sorted = append(sorted, pivot)
sorted = append(sorted, zeroPivot(greater, depth+1)...)
return sorted
}
sortedArray := zeroPivot([]int{1, 2, 3, 4, 5, 6, 7, 8}, zeroPivotMaxDepth)
fmt.Printf("sorted array: %vn", sortedArray)
fmt.Printf("max stack depth: %dn", zeroPivotMaxDepth)
As we can see, zeroPivotMaxDepth is instantiated before the anonymous function definition, and then it is referenced in the code. Finally, it is recursively passed in to the further sorted commands and incremented when it goes down a level.
Of note, I started the count at 1 to emulate the above example.
When I run this, I get a stack depth of 8:
➜ go run main.go (current-context is not set)
sorted array: [1 2 3 4 5 6 7 8]
max stack depth: 8
And if I update the array to []int{1, 8, 3, 4, 6, 2, 5, 7}, we should see the stack depth change:
➜ go run main.go (current-context is not set)
sorted array: [1 2 3 4 5 6 7 8]
max stack depth: 6
Middle index Pivot
Now let’s do the same thing but instead we’re going to use the middle pivot. This is essentially the best case for divide and conquer. I’ll just show the updated code to keep it a little more concise, but note the algorithm changing based on the pivot location.
middlePivotMaxDepth := 1
var middlePivot func([]int, int) []int
middlePivot = func(nums []int, depth int) []int {
if depth > middlePivotMaxDepth {
middlePivotMaxDepth = depth
}
if len(nums) < 2 {
return nums
}
pivotIndex := len(nums) / 2
pivot := nums[pivotIndex]
lower := []int{}
higher := []int{}
for i, v := range nums {
if i == pivotIndex {
continue
}
if v <= pivot {
lower = append(lower, v)
} else {
higher = append(higher, v)
}
}
sorted := []int{}
sorted = append(sorted, middlePivot(lower, depth+1)...)
sorted = append(sorted, pivot)
sorted = append(sorted, middlePivot(higher, depth+1)...)
return sorted
}
And when we run this, here’s what we see below.
When it’s already sorted:
➜ go run main.go (current-context is not set)
sorted array: [1 2 3 4 5 6 7 8]
max stack depth: 4
And when it’s not:
➜ go run main.go (current-context is not set)
sorted array: [1 2 3 4 5 6 7 8]
max stack depth: 5
And that’s it 🙂 Hope it was interesting!