# Playing With Code: Insertion Sort in Swift

Written by Reinder de Vries on August 6 2020 in App Development, Swift

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

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!

#### Learn how to build iOS apps

##### Get started with iOS 14 and Swift 5

Sign up for my iOS development course, and learn how to build great iOS 14 apps with Swift 5 and Xcode 12.

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

1. First, we’re taking `55` out. This frees up a space in the array.
2. 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.
3. 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.)
4. Then, we’re comparing `55` against `40`. 40 is smaller than 55, so now we’re inserting `55` into the free spot.
5. 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!

``````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 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?

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:

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

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.

#### Learn how to build iOS apps

##### Get started with iOS 14 and Swift 5

Sign up for my iOS development course, and learn how to build great iOS 14 apps with Swift 5 and Xcode 12.

Hi, I'm Reinder.
I help developers play with code.

## Get the Weekly

Get iOS/Swift tutorials and insights in your inbox, every Monday.
• This field is for validation purposes and should be left unchanged.

## Swift Sandbox

Code Swift right in your browser!
Go to the Swift Sandbox

### Reinder de Vries

Reinder de Vries is a professional iOS developer. He teaches app developers how to build their own apps at LearnAppMaking.com. Since 2009 he has developed a few dozen apps for iOS, worked for global brands and lead development at several startups. When he’s not coding, he enjoys strong espresso and traveling.

×

Build great iOS apps
Learn how in my free 7-day course

• This field is for validation purposes and should be left unchanged.