Digging deeper, sorting out insertion sort in Swift

When I first started programming I didn’t start learning about advanced data structures or algorithms, instead, I started as most developers do by building an extremely simple project while ‘googling’ my way forward to reach my goal. My first Swift app was just a simple storyboard application that used a button to hide a label. Even though this app was ridiculously simple I still remember the excitement when I finally got it to work. Then I would try something a little bit harder; to change the background color every time I pressed the button. I would continue like this by building projects I found interesting, until eventually having my own apps on the App Store.

I love this approach of learning by building projects, even if I’m not super familiar in a specific language or library and to keep on hacking and googling until I learn it. I think this is a very important mindset of a developer, to not be afraid to try new technologies and not be afraid of being wrong. I personally think that to learn to love to code you have to build interesting programs, rather than studying how to do it beforehand.

One of the downsides of this approach is that you generally skip the boring parts which are fundamental for a deep understanding of programming. For example, most people learning to build web apps today would probably jump directly into the magical world of Ruby on Rails, without actually understanding what’s going on under the hood. This struck me at the end of my first six weeks here at the Web Developer program at the Flatiron School. We started off learning Rack and Sinatra before moving into Rails. Even though we never really used Rack or Sinatra for our final web applications, they provided us with a really strong foundation to understand the magic of Rails, which made us all better Rails developers. After realizing this, I have slightly modified my idea about the best way of learning to code. I still believe that the absolute best way to learn to code is by building a project you’re really interested in. BUT It is also extremely important to take a step back from building amazing programs to really understand the fundamentals.

So that is exactly what I’m going to do now. Even though I’ve been programming in Swift for the last four years, I have never written a proper sorting algorithm. Thus I thought it was time to write this blog to step up my foundation in Computer Science by building an insertion sort algorithm in Swift.

An insertion sort algorithm works by having a key index pointing at the second element in the array, i.e index 1. We start at the second element of the array since the first one by definition already is sorted (a single element in itself is always sorted). The algorithm then compares this element to the element to the left of it, if the element to the left is bigger than the element, we swap the elements. We update this swapping until the element to the left is smaller or equal to the element. Lastly, we increment the key and repeat the same process.

An illustration of how insertion sort works.

Below is my implementation of insertion sort in Swift:

Let’s walk through the above code together:

1. The for loop loops over all the values of our key. It starts off at index 1 and then keeps on looping until it reaches the maximum index of the array, and thus the last element that we want to sort.
2. Here we create and loop over the range 1 to the current value of our key variable. Since we want to start with comparing the element with the highest index first, i.e the index that our key variable equals, we reverse the order of the range.
3. We then check if the current element is smaller than the element to the left. If it’s smaller, we than use the swapAt function to swap the elements. We will then keep on looping until the element on the left side of the current element is not smaller and will then break out of the loop, and then move on to the next key value.

Hopefully, you followed along how the insertion sort algorithm works, but I hope that the biggest takeaway from this blog post is the way you learn how to code. Keep on building your exciting projects, but take some time off now and then to dig a bit deeper inside the mechanics of your code.

Hope you enjoyed this blog! Stay curious!