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

Leave a Reply

Your email address will not be published. Required fields are marked *