Quicksort the Swift way

Quicksort algorithm is in my opinion the most elegant sorting algorithm. In this article I'll show you how to use Swift playgrounds to make fun writing and understanding algorithms.

Quicksort basics

Quicksort is in average case one of the quickest sorting algorithms in the world. It is a divide and conquer algorithm that uses recursion to divide problem to smaller ones, put one element in the right position and and recursively sort sub-arrays. In provided links you'll find solid backgrounds if you don't have them already.

Playgrounds

Swift interactive playgrounds are a fast way to prototype, build code snippets and experiment without an existing app. You can freely test your ideas and see the results calculated in real time. If you havent't you should definitely watch this WWDC 2014 video about them.

To create playground in Xcode select:
File → New → Playground and name it e.g. Quicksort.

Quicksort in Swift

Preparation

Let's prepare some test data:

var list = [8,1,55,34,13,8,5,0,1,3,2,21]  

Yes, this is a Fibonacci sequence but in random order.

We will use element at index 0 as a pivot (it's not the best choice but it will simplify our code and when you understand the basics you can easily change the pivot choice implementation).

Also instead of swapping elements in the same array we will use filter function to do the job.

Attempt 1

First implementation of Quicksort in Swift might look like this:

func quicksort1(list:[Int]) -> [Int] {  
    if list.count == 0 {
        return []
    }

    let pivotValue = list[0]
    let smaller = filter(list, { $0 < pivotValue })
    let greater = filter(list, { $0 > pivotValue })

    return quicksort1(smaller) + Array(arrayLiteral:pivotValue) + quicksort1(greater)
}

You can call it for our sample data:

quicksort1(list)  

And see the results: [0, 1, 2, 3, 5, 8, 13, 21, 34, 55].

Quicksort Swift Playground with first implementation

What happens here?

  1. First of all we define a stop condition for further recursion calls so it doesn't run forever. If the list is empty simply return empty list (which is sorted by definition).

  2. Next, select first element and treat it as a pivot value.

  3. Select all smaller numbers by filtering the list.

  4. Select all greater numbers the same way.

  5. Make 2 recursion calls and concatenate results in place - this is the most tricky part:

    • we call quicksort(smaller) so the execution will stop here and actually dive inside this call and will do so forever... until it meets our stop condition!
    • it concatenates the sorted smaller part with our pivot value and makes the same calls for a greater part.
    • remember that each single call consists of all these 3 steps (it's the recursion, right? ;) ).

If it's not easy to understand it's where the Swift Playground may help us. Let's append our code so we can see our variables:

let smaller = filter(list, { $0 < pivotValue })  
smaller  
let greater = filter(list, { $0 > pivotValue })  
greater  

Press small + button next to the (10 times) labels in pivotValue, smaller and greater lines so we can see live results.

Quicksort Swift Playground show results

You should see something similar to this:

Quicksort Swift Playground results

Analysis

You should see the graph of pivotValue and table of smaller list values. Let's analyze it.

  1. First pivot value is 8 as we expected (first element of the list).
  2. In this step smaller contains [1, 5, 0, 1, 3, 2] so all of them are actually smaller - our filter works good.
  3. greater contains [55, 34, 13, 21] so second filter works great.
  4. In second step we must remember the algorithm is called recursively for smaller values, so in our case it's quicksort([1, 5, 0, 1, 3, 2]). Pivot is 1, smaller is [0] and greater is [5, 3, 2].
  5. Third step is called on [0] list so after selecting pivot, smaller and greater lists are empty ([]), so the last line looks like: return quicksort([]) + [0] + quicksort([]). We have a stop condition so calls is reduced to return [] + [0] + [] which returns sorted 1-element array: [0] and the algorithm jumps one step back to the point: return [0] + [1] + quicksort([5, 3, 2]).
  6. Performing all these steps will give us final results of: [0, 1, 2, 3, 5, 8, 13, 21, 34, 55].

Drawback

Presented solution has one weak point: it doesn't work with duplicated entries. If we choose only smaller and greater elements there's no way to preserve the same numbers as one of the pivot values. In our case we miss one 1.

We cannot simply use <= and >= comparisons because it will fall into loop. We have to be smarter.

Attempt 2

We will simply remove the pivot value after we select it and then we will use <= operator for a smaller set. Fixed algorithm might look like this:

func quicksort2(list:[Int]) -> [Int] {  
    if list.count == 0 {
        return []
    }

    let pivotValue = list[0]
    let listStripped = list.count > 1 ? list[1...list.count-1] : []
    let smaller = filter(listStripped, { $0 <= pivotValue })
    let greater = filter(listStripped, { $0 > pivotValue })

    return quicksort2(smaller) + Array(arrayLiteral:pivotValue) + quicksort2(greater)
}

You can call it for our sample data:

quicksort2(list)  

and it prints full fibonacci sequence with all numbers! [0, 1, 1, 2, 3, 5, 8, 8, 13, 21, 34, 55].

listStripped variable contains the whole list without first (pivot) element. That's why I told you before it will be easier :)

Attempt 3

Final ride - for all that lasted to the end: maybe not the most elegant, but single line quicksort written purely in Swift that can handle duplicated numbers:

func quicksort(list:[Int]) -> [Int] { return countElements(list) == 0 ? [] : quicksort(filter(list.count > 1 ? list[1...list.count-1] : [], { $0 <= list[0] })) + Array(arrayLiteral: list[0]) + quicksort(filter(list.count > 1 ? list[1...list.count-1] : [], { $0 > list[0] })) }  

Who said that algorithm must be long to do the job? Sometimes one-liner is more than enough. And you can easily use it as your cover photo ;)

Benchmark

I wrote a simple Mac app that uses written algorithm to benchmark it with existing one.

import Foundation

func quicksort(list:[Int]) -> [Int] { return countElements(list) == 0 ? [] : quicksort(filter(list.count > 1 ? list[1...list.count-1] : [], { $0 <= list[0] })) + Array(arrayLiteral: list[0]) + quicksort(filter(list.count > 1 ? list[1...list.count-1] : [], { $0 > list[0] })) }

var array = [Int]()  
for i in 1...100000 {  
    array.append(Int(arc4random()))
}

var d1 = NSDate()  
quicksort(array)  
println(NSDate().timeIntervalSinceDate(d1))

d1 = NSDate()  
sorted(array)  
println(NSDate().timeIntervalSinceDate(d1))  

Results are crushing:

38.33 seconds for quicksort

0.70 second for built-in sorted

So you definitely shouldn't use it in production code!

Why the results are so bad? Well, probably due to creation of so many arrays during the execution. Instead of swapping elements we filtered original array, created the copy without pivot value etc. It all can be fixed but it wasn't the point of this article.

In the end I hope you enjoyed this quick Swift Playgrounds journey :)

Source code

You can find source code for playground on GitHub.

More?

Do you like this article? Share it on Twitter, Facebook, Google+ or simply leave a comment below. You can also visit our website www.sigmapoint.pl to see what else we can offer. Thanks!

comments powered by Disqus