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:

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:

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:

I can make it implement Comparable in an extension:

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

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

And sort it like this:


Here is a playground containing the code: QuickSort.playground

Leave a Reply

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