Playing With Code: Insertion Sort in Swift

By Aasif Khan | Last Updated on May 12th, 2023 9:21 pm | 5-min read

Let’s play with code! In this tutorial, 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. What better way to improve your Swift programming skills, than tinkering with sorting algorithms?

The What and Why of Sorting Data
Coding The Insertion Sort Algorithm in Swift
Putting Everything Together
Further Reading

The What and Why of Sorting Data

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 example. 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 collection – 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(n2). 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!

How Does Insertion Sort Work?

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:

We’re iterating over every item in the array, from left to right. We can skip the first item, because it’s an already sorted sublist.
Every item is compared against the sublist of items that we’ve already sorted, from right to left, starting with the current item.
When the algorithm encounters a number that’s greater than the current item, that number is shifted one position to the right.
When it encounters a number that’s smaller than the current item, or we’ve reached the end of the sublist, the current item is inserted.

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?

Here’s what happens:

First, we’re taking 55 out. This frees up a space in the array.

Then, we’re comparing 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.

Then, we’re comparing 55 against 70. 70 is greater than 55, so we’re shifting 70 one position to the right. (Same step as before.)

Then, we’re comparing 55 against 40. 40 is smaller than 55, so now we’re inserting 55 into the free spot.

Done! The right spot for 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(n2) 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(n2).

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!

Coding The Insertion Sort Algorithm in Swift

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..

index, which is the array index number we’re currently iterating

value, which is the array value we’re currently inspecting

position, 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?

Remember that as we’re iterating over the numbers, we’re going to inspect the sublist of sorted numbers before it.
We’ll do so by starting at 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.
But that’s not everything! We only want to go backwards if the number at the position we’re inspecting is greater than the current value.
That’s the second part of the loop. If the inspected number is greater than the number at the current position, shift that number one position to the right with 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:

Determine the sorted position for each array item, by looping over the array
By shifting items that are greater than the current item, to the right
Until an item is smaller than the current item, then just insert it

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.

Putting Everything Together

Here’s the algorithm we’ve coded so far. Give it a try! Do you understand how it works?

var numbers = [70, 36, 40, 95, 22, 55, 26]

for index in 1.. 0 && numbers[position – 1] > value {
numbers[position] = numbers[position – 1]
position -= 1
}

numbers[position] = value
}

print(numbers)

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!

var numbers = [70, 36, 40, 95, 22, 55, 26]

print(“We’re going to sort these numbers: \(numbers)”)

for index in 1.. 0 && numbers[position – 1] > value
{
print(“– \(numbers[position-1]) > \(value), so shifting \(numbers[position-1]) to the right”)

numbers[position] = numbers[position – 1]
position -= 1

print(“-> \(numbers)”)
}

print(“– Found sorted position of \(value) is \(position), so inserting”)

numbers[position] = value

print(“-> \(numbers)”)
print(“”)
}

print(numbers)

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:

func insertionSort(_ input: [T], by comparison: (T, T) -> Bool) -> [T]
{
var items = input

for index in 1.. 0 && comparison(items[position – 1], value) {
items[position] = items[position – 1]
position -= 1
}

items[position] = value
}

return items
}

var sorted = insertionSort([70, 36, 40, 95, 22, 55, 26], by: >)
print(sorted)

var names = insertionSort([“Marvin”, “Arthur”, “Zaphod”, “Trillian”, “Eddie”], by: { $0 < $1 }) print(names) What’s going on here? The insertion sort algorithm didn’t change, but a few other things did:

The insertionSort(_:by:) function uses the generic placeholder T. And the type T needs to conform to Comparable, such as Int or String.
The type of the 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.
The 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.