#### 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! And what better way to improve your Swift programming skills, than tinkering with *sorting* algorithms.

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.

Ready? Let’s go.

- The What And Why Of Sorting
- How Does Insertion Sort Work?
- Coding The Insertion Sort Algorithm
- Putting Everything Together
- Further Reading

*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

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:

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

And 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(n ^{2})* time complexity from. In the worst case scenario, it needs to compare every item against every other item. Differently said,

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

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

{

let value = numbers[index]

var position = index

while position > 0 && numbers[position - 1] > value {

numbers[position] = numbers[position - 1]

position -= 1

}

numbers[position] = value

}

print(numbers)

for index in 1..<numbers.count

{

let value = numbers[index]

var position = index

while position > 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..<numbers.count

{

let value = numbers[index]

var position = index

print("- Inspecting value: \(value) at position: \(position)")

while position > 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)

print("We're going to sort these numbers: \(numbers)")

for index in 1..<numbers.count

{

let value = numbers[index]

var position = index

print("- Inspecting value: \(value) at position: \(position)")

while position > 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<T: Comparable>(_ input: [T], by comparison: (T, T) -> Bool) -> [T]

{

var items = input

for index in 1..<items.count

{

let value = items[index]

var position = index

while position > 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)

{

var items = input

for index in 1..<items.count

{

let value = items[index]

var position = index

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

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:

- How To: Shuffling An Array In Swift Explained
- Generics in Swift Explained
- Let’s Solve The FizzBuzz Challenge In Swift
- Get Started With Xcode Playgrounds
- How To Become A Professional iOS Developer

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.

- How To Learn iOS App Development
- 27 App Marketing Strategies That Just Work
- How To Make An App (In 9 Steps)
- For Loops In Swift (How To)
- How To: Pass Data Between View Controllers In Swift (Extended)
- How To Solve SIGABRT Error In Xcode
- Working With Codable And JSON In Swift
- » Show latest