I've always been fascinated by algorithms. Much of what makes software engineering challenging is finding the right way to do something. When processing large amounts of data, finding the right algorithm can make the difference between accomplishing a task or failing entirely.
Today I'd like to go over a useful algorithm for sorting an array of items: insertion sort.
Introduction
Insertion sort is one of the simplest algorithms, but it's also extremely useful. Here's how it works:
Given an array of unsorted items (A):
- Grab the first item from A
- Insert this item into a new array, called B
- Grab the next item from A
- Insert this item into the correct place in B
- Repeats steps 3 and 4 until the array B is a sorted representation of array A
The algorithm is called insertion sort because you're inserting one item at a time into the correct position into a new array.
Example
Given an array of numbers, A:
A: [5, 7, 1, 4, 2]
Pick the first number, 5, and insert it into a new array, B:
A: [7, 1, 4, 2]
B: [5]
Now grab the next number, 7, and insert it into the correct spot in B:
A: [1, 4, 2]
B: [5, 7]
Now repeat this two-step process until A is empty:
A: [4, 2]
B: [1, 5, 7]
Next...
A: [2]
B: [1, 4, 5, 7]
Next...
A: []
B: [1, 2, 4, 5, 7]
And we're done! Note that B is now a sorted array of items from the array A.
Sorting In-Place
This algorithm may sound like you need two arrays, but in reality you could accomplish this with just one. To do this, you perform the algorithm in-place by keeping track of which part of the array is sorted. Here's an example:
We start the algorithm by setting the index (i in the example) to zero, meaning it's at the beginning of the array. I will represent i by a |:
Initial state:
A: [|5, 7, 1, 4, 2]
Step 1:
A: [5 | 7, 1, 4, 2]
Step 2:
A: [5, 7 | 1, 4, 2]
Step 3:
A: [1, 5, 7 | 4, 2]
Step 4:
A: [1, 4, 5, 7 | 2]
Step 5:
A: [1, 2, 4, 5, 7 |]
Implementing the Insertion
I mentioned inserting the item at the right index in the array. How would we go about implementing that?
Let's say we're at Step 3 from above, and the array looks like this:
A: [1, 5, 7 | 4, 2]
The next item to sort is 4, and in this case it needs to be inserted between the 1 and the 5.
One way to accomplish this would be to look at the last item in the array, 7, and compare it with the next item, 4. Is the last item greater than the next item (7 > 4)? Yes, so we swap the two.
A: [1, 5, 4, 7, | 2]
Notice we still don't have a sorted array, as 4 is not greater than 5. So, we swap these two elements, and get this:
A: [1, 4, 5, 7, | 2]
Next, we check if the previous element, 1, and see if it's greater than our element, 4. It's not, so we're finished!
Swift Implementation (Slow)
Here's an example of how you could implement this in Swift. For a faster implementation, and to see how Apple implemented insertion Sort in the Swift standard library, keep reading!
And one with inline explanation:
Note that we start the index marker i at location 1, not 0, because starting at 0 would mean swapping the first item from the unsorted pile into the sorted pile, which doesn't get us anything.
Improving Performance by Removing Swaps
In the above example we're comparing unsorted items to sorted items and then swapping them as needed. To make this faster, we can remove the swap call entirely, and instead shift the items. Essentially, here's what we're doing:
- Remember the next unsorted item, X
- Loop through the sorted items, shifting them all to the right (instead of swapping them, as shown above) until you find the right spot for X
- Insert X at this location
- Repeat steps 1-3 until the last unsorted item is sorted
Here's what that might look like in Swift:
And the compact version:
Sorting Arrays of Custom Objects
To make our function accept arrays of non-Int objects, we can use Swift Generics like so:
An example of this in use would be:
An Even Cleaner Approach
Here's an approach that uses the Comparable protocol instead of requiring a closure. This will work with arrays of anything that conforms to Comparable.
Update 4/21/16: I should note that Apple uses insertion sort in their own sort() function if the array size is less than 20 items. Check out that implementation here.
When To Use Insertion Sort
Insertion sort is extremely fast for small and already sorted arrays. That seems goofy to say: why would you care how fast a sorting algorithm is on an array that's already sorted? Often times you won't know what data your system will receive, and sometimes you'll receive arrays that are already sorted or almost sorted. If this is the case, insertion sort performs better than other algorithms.
There are two nested loops in insertion sort, so the average performance is O(n^2). The best case performance is O(n).
References
The open source Swift Algorithm Club repository provided much of the explanation here - if you haven't had a chance to check it out, you should!
Update 4/21/16: Added a note explaining how insertion sort is used under some conditions in the Swift sort() function in the standard library. Check that out here.