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.

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`

.

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.

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]`

.

What happens here?

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).Next, select first element and treat it as a pivot value.

Select all smaller numbers by filtering the list.

Select all greater numbers the same way.

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? ;) ).

- we call

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.

You should see something similar to this:

You should see the graph of `pivotValue`

and table of `smaller`

list values. Let's analyze it.

- First pivot value is
`8`

as we expected (first element of the list). - In this step
`smaller`

contains`[1, 5, 0, 1, 3, 2]`

so all of them are actually smaller - our filter works good. `greater`

contains`[55, 34, 13, 21]`

so second filter works great.- 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]`

. - 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])`

. - Performing all these steps will give us final results of:
`[0, 1, 2, 3, 5, 8, 13, 21, 34, 55]`

.

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.

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 :)*

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 ;)

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 :)

You can find source code for playground on GitHub.

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!

]]>