Quicksort in Swift

While looking over some of my notes on algorithms today I came across the quick sort algorithm. Just for fun, I set out to implement it in Swift. Because of the built-in filter function it’s possible to write this algorithm very elegantly.

func quickSort(_ arr: [Int]) -> [Int] {
var arr = arr

guard arr.count > 1 else { return arr }

let pivot = arr.remove(at: arr.count/2)
let pivotArr = [pivot]

let leftArr = arr.filter { $0 < pivot}
let rightArr = arr.filter { $0 >= pivot}

return quickSort(leftArr) + pivotArr + quickSort(rightArr)

What happens here is that we use the filter function to partition the input array into two. First we remove the pivot element from the input array. In order to do that, we have to assign the input array to a (var) variable inside the function, since as of Swift 3.0, all function parameters are lets and therefore constant.
Then we simply apply the filter function twice to obtain the subarray with elements smaller than the pivot and the subarray with elements greater or equal to the pivot.
Finally we return the sorted array, by recursively calling the function on the left subarray concatenating the pivot element and then concatenating the result of a recursive call to the right subarray.

Swift Closure Syntax

If the braces and the contents after it seem a bit strange to you, you can familiarize yourself with Swift closure syntax here. The braces after the filter functions are called trailing closures. In Swift, if a closure is the last argument to a function you are allowed write the closure outside of the function parentheses. When you do that, you also omit the argument label of the closure. For a function with several arguments this would look something like this someFunc(firstArg: value) {// this is the body of the trailing closure}.
But we can do even better. If the closure is the only argument of the function, you can even omit the function parentheses after the function name, which for the Array.filter function would look like this: Array.filter {//body of the trailing closure}.
So what’s up with $0?
Swift provides shorthand argument names to all the arguments inside a closure. The names are simply assigned by position: $0, $1, $2 etc. This allows you to write write terse yet readable code.

For all the elegance that this filter- based solution exudes it should be noted, that this algorithm is nowhere near as efficient as the traditional in-place quick sort implementations, either with the Lomuto or with Hoare’s partitioning scheme. That is because we repeatedly create new arrays as outputs from the filter functions instead of working with the same array.