Learn how to build iOS apps
Get started with iOS 13 and Swift 5
Sign up for my iOS development course, and learn how to build great iOS 13 apps with Swift 5 and Xcode 11.
Let’s play with code! In this article, we’ll discuss how insertion sort works. It’s one of the simplest sorting algorithms we have, which makes it the perfect candidate for some leisurely Swift coding. And what better way to improve your Swift programming skills, than tinkering with sorting algorithms.
Ready? Let’s go.
Sorting is the act of arranging items systematically, according to a predetermined rule or order. You can sort numbers from biggest to smallest, people’s names from A to Z, and bits of rope by length.
When building apps, you might need to sort data that’s user-facing. The names in an address book, for example. You sort the list of names from A to Z and present them to the user.
At other times, sorting happens behind the scenes. Many search algorithms can more efficiently search a list when it’s already sorted, for instance. You can imagine that Google has an alphabetically sorted index of search phrases, so it can quickly find which website fits the search term “sports shoes.”
An algorithm is best defined as “a sequence of steps, that takes input, and produces output.” As such, a sorting algorithm takes a list – an array – processes it, and returns a sorted array. In some cases you can provide additional parameters, like a comparison function.
An important attribute of a sorting algorithm is its time complexity. In short, time complexity expresses the time an algorithm takes to complete relative to the size of the input. Big O notation is used to describe time (and space) complexity. An efficient sorting algorithm, such as quicksort, has a worst-case time complexity of O(n log n).
It’s worth noting that the Swift uses Introsort as its sorting algorithm of choice. It’s a hybrid algorithm that combines quicksort and heapsort adaptively, to provide a generic algorithm that performs well on average.
The algorithm we’re working with today – insertion sort – has a complexity of O(n^{2}). When the size of the input array doubles, the time it takes to run the insertion sort algorithm quadruples! You can imagine this is a problem for large datasets, but for an exercise like this one it’s just fine.
Let’s get started with insertion sort!
Sign up for my iOS development course, and learn how to build great iOS 13 apps with Swift 5 and Xcode 11.
It’s easiest to compare insertion sort with sorting a hand (or deck) of playing cards.
Imagine you’ve got a hand with 5 playing cards. To sort your cards, you take out a card, and determine its sorted place among the rest of the cards. You do this for every card to sort your entire hand.
This is where insertion sort gets its name, because you’re taking out items and putting them back in their sorted spots. For every item in the array, we’re determining its sorted spot, and inserting the item there.
Let’s discuss the insertion sort algorithm. We’re going to sort this array of integer numbers:
[70, 36, 40, 95, 22, 55, 26]
We’ll iterate over every item in the array, from left to right, except for the first item. The items we’ve already sorted will end up at the left of the array.
Here’s how it works:
Let’s look at a visual example:
In every step, from top to bottom, the orange item is compared against the blue items, and inserted at the right spot. So… what’s the right spot?
Here’s a closer look at step 5. The number 55
needs to get inserted somewhere in the sorted sublist. How?
And here’s what happens:
55
out. This frees up a space in the array.55
against 95
, the item before it. 95 is greater than 55, so we’re shifting 95
one position to the right – into the free space.55
against 70
. 70 is greater than 55, so we’re shifting 70
one position to the right. (Same step as before.)55
against 40
. 40 is smaller than 55, so now we’re inserting 55
into the free spot.55
is between 40
and 70
.This same process is repeated for every item in the array. And that’s where the insertion sort gets its O(n^{2}) time complexity from. In the worst case scenario, it needs to compare every item against every other item. Differently said, two nested loops – a telltale sign of O(n^{2}).
Why can we skip over the first item? Even though number 70
isn’t in its final sorted spot, it’ll get shifted to the right because of comparisons with the other numbers. So, you could say that a sublist of one item is already sorted!
It’s time to actually code this algorithm. Let’s get to it!
Based on the mechanism we’ve discovered, we can code the insertion sort algorithm step by step. Most of the pieces are already in place!
Let’s start with the unsorted numbers. Like this:
var numbers = [70, 36, 40, 95, 22, 55, 26]
We now need some code to iterate over these numbers, starting at the second item in the array, up to the end of the array. Here’s how:
for index in 1..<numbers.count
{
}
This is a for loop, and it loops over a range from 1
to numbers.count
– but not including numbers.count
. When numbers
has 7 items, the range 1..<numbers.count
is 1..<7
, which is 1 to 7, not including 7. We need to be so strict about this, otherwise we’ll get an Index out of bounds error.
Next up, inside the loop we need to keep track of two things: the current array item we’re inspecting, and the position of the place at which we want to insert this item. Like this:
let value = numbers[index]
var position = index
The value
constant will contain each of the numbers, as we’re iterating over them. The position
variable will initially contain the current index, but as you’ll soon see, we’re going to change this position based on the comparisons with the sorted sublist.
At this point we have 3 bits of information at our disposal:
index
, which is the array index number we’re currently iteratingvalue
, which is the array value we’re currently inspectingposition
, which is the index we’re going to insert value
at (after we’ve determined what this sorted position is)Next up, we’re going to code that inner loop that iterates over the sorted sublist. Here it is:
while position > 0 && numbers[position - 1] > value {
numbers[position] = numbers[position - 1]
position -= 1
}
This is a while
loop. It’ll keep looping as long as its expression is true
. It’s perfect if you don’t know how many times a loop needs to run (as opposed to a for
loop).
How does that while
loop work?
index
and counting backwards, until we reach 0
. That’s the first part of the loop. While position
is above zero, subtract 1
from position
with position -= 1
.numbers[position] = numbers[position - 1]
.Finally, once the sorted position for the current item is determined, we can simply assign the value to its new place. Like this:
numbers[position] = value
The items that are greater than value
have been shifted to the right. And the while
loop stops when it encounters a value smaller than the current value. As such, we can now insert the current value in the free space.
This is the most difficult step in this algorithm. It’s worth looking over once more!
Let’s check it out from a different point of view. You know that the insertion sort relies on three principles:
The while
loop does two things. It keeps track of the position
and it shifts array items to the right. It only does this if position
is greater than zero (a “backstop”) and if the inspected value is greater than the current value.
Technically, the array is iterated in two directions. First, from left to right for every item. And then the nested loop walks backwards from the current item, over the items that have already been sorted.
Imagine you’re physically walking over this array yourself, kinda like hopscotch, stepping in each of the squares. In every step, you’re taking the number beneath your feet.
You look behind you to compare this number with all the numbers you’ve previously sorted. You can’t just insert the number, so to make room, you shift the previous numbers towards yourself until you’ve made some space at the exact right spot.
Here’s the algorithm we’ve coded so far. Give it a try! Do you understand how it works?
Here’s a quick question: Can you change one character, to make the sorting algorithm sort from biggest to smallest number instead?
And here’s the same algorithm, with verbose print()
lines added that walk you through the steps. Give it a try!
Of course, the big question is: Can we turn this algorithm into a function that works with any data type?
Yes! As long as the input data for the algorithm conforms to the Comparable
protocol, you can sort anything you want. And we’ll even throw in a comparison closure, for good measure.
Here we go:
What’s going on here? The insertion sort algorithm didn’t change, but a few other things did:
insertionSort(_:by:)
function uses the generic placeholder T
. And the type T
needs to conform to Comparable
, such as Int
or String
.input
parameter, and the function return type, are both [T]
. Whatever type you put in, will also come out. They’re both arrays, of course.comparison
parameter takes a closure of type (T, T) -> Bool
. This means that the closure has two inputs T
and returns a boolean.Within the algorithm we’re calling the comparison
closure and provide it the two values that need to be compared. Remember how we used that comparison to control the sorting, in the algorithm? Thanks to the closure, you can now provide your own comparison function!
You’ll see that for the sorted
and names
arrays, at the end. For sorted
we’re merely providing the greater-than >
logical operator. This operator takes two inputs, the left-hand and right-hand sides, and returns a boolean. The implementation is essentially exactly the same as what we had before.
And for names
we’re providing the closure { $0 < $1 }
. It uses the $n
shorthand to reference the input parameters of the closure, and compares them with the less-than <
logical operator. Just as before, this compares the two array elements against each other to determine their sorting order.
Awesome! Once you put your mind to it, these algorithms aren’t that hard to comprehend. And it’s pretty cool to go from an algorithm on paper, to working code, to writing something you can use in your day-to-day programming.
Want to learn more? Check out these resources:
Sign up for my iOS development course, and learn how to build great iOS 13 apps with Swift 5 and Xcode 11.
Hi, I'm Reinder.
I help developers play with code.
Build great iOS apps
Learn how in my free 7-day course
No spam, ever. Unsubscribe anytime. Privacy Policy