# One of those times when everything clicks

Let me tell you a little story…

The other day, while looking for an implementation of a binary tree online, I stumbled upon the fantastic Swift Algorithm Club. I didn’t study Computer Science, so I have learnt everything I know about algorithms, which is not too much, by myself. That’s why I find efforts like the Swift Algorithm Club extremely useful. Kudos, 👍 👍 👍 👍 👍.

But back to my story. Why on earth was I looking for an implementation of a binary tree? Because I enjoy doing code katas regularly. It is a good way to learn new languages (i.e. Scala), new practices (that’s how I started doing TDD a few years back) or just kill some time doing something better than just watch TV.

The thing is, one thing lead to another, and instead of writing a binary tree, I started writing a function to quick sort an array.

Now, Swift, as you are aware, supports generics, so my first draft of the implementation was something like this:

```extension Array where Element: Comparable {
func quicksort() -> [Element] {
guard count > 1 else {
return self
}

let centerIndex = self[count/2]
let left = self.filter{\$0 < centerIndex}
let center = self.filter{\$0 == centerIndex}
let right = self.filter{\$0 > centerIndex}

return left.quicksort() + center + right.quicksort()
}
}```

Why an extension? Well, it seems like quicksort() should be an instance method, rather than a free function. Encapsulation FTW, I guess.

But an extension makes total sense (and here is when things start clicking together) because I can sort any array of Comparable elements:

```let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
let sortedList = list.quicksort()
//[-1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27]

let listWords = [ "zoo", "car", "cesar", "abalone"]
let sortedLIstWords = listWords.quicksort()
//["abalone", "car", "cesar", "zoo"]```

So, would it be possible to apply the same sorting algorithm to an array of a custom type? Well, it should, as long as that type implements Comparable.

So here is my type:

```struct Person {
let name: String
let surname: String
}```

I can make it implement Comparable in an extension:

`extension Person: Comparable {}`

And implement the necessary methods as free functions (yes, the implementation is very naive, but I just wanted to test my hypothesis as quick as possible):

```func ==(lhs: Person, rhs: Person) -> Bool {
return lhs.surname + lhs.name == rhs.surname + rhs.name
}
func <(lhs: Person, rhs: Person) -> Bool {
return lhs.surname + lhs.name < rhs.surname + rhs.name
}
func <=(lhs: Person, rhs: Person) -> Bool {
return lhs.surname + lhs.name <= rhs.surname + rhs.name
}
func >(lhs: Person, rhs: Person) -> Bool {
return lhs.surname + lhs.name > rhs.surname + rhs.name
}
func >=(lhs: Person, rhs: Person) -> Bool {
return lhs.surname + lhs.name >= rhs.surname + rhs.name
}```

So, I can build an array of people like this:

```let me = Person(name: "Cesar", surname: "Tardaguila")
let him = Person(name: "Alan", surname: "Zooland")
let her = Person(name: "Alan", surname: "Alimony")
let theGuyOverThere = Person(name: "Alan", surname: "Betatester")

let people = [me, him, her, theGuyOverThere]```

And sort it like this:

```let sortedPeople = people.quicksort()
// [{name "Alan", surname "Alimony"}, {name "Alan", surname "Betatester"}, {name "Cesar", surname "Tardaguila"}, {name "Alan", surname "Zooland"}]```

Neat!

Here is a playground containing the code: QuickSort.playground