Swift: Insertion Sort with a Functional Approach
Just in case if you haven’t read any of my other post I am aware of .sort() & .sorted() in Swift, this is just to learn the basics of functional programming.
Disclaimer: If you understand insertion sort jump to “Standard approach” to see a standard way of doing it or “Functional approach” to see my functional version.
Insertion sort is a classical sorting algorithm where we have an array of unsorted objects. We take the first object and put it into a sorted array, we then take object two and put it into its correct place in the sorted array. We then take object three and place it at the correct place in the array. We continue following this pattern until the unsorted array is empty. This algorithm like selection sort has a runtime of n * n or n squared. It has that runtime because it requires two loops or two recursive functions to complete the algorithm.
The standard approach allows us to use variables and loops. First like in insertion sort we have to extend Array so that we can call this function on an array. We will need to extend it where the Elements of the array are Comparable.
1 We will have to make sure there is more than 1 object in the array if not then just return the array.
2 We will then have to iterate from the second element until the end, because we already have the say that the first element is sorted. For that we can use a simple for loop. So now our function becomes this.
3 Now the fun begins. We will make a copy of what index we are currently on because this will mutate and “a” in the for loop is a let. Then we will get a temporary value which will be the current object at the current index (b). Then we will go into our last loop that will continue as long as the current index (b) is above zero & we are either above or below the value at the current index. This depends if we want to go in ascending or descending order. Next, inside the last loop, we will lower all the values of the array by 1, and lower the index by 1. Lastly, we will add the value of the object at the correct index (b). That will complete the function leaving us with this.
That’s it for the standard approach. Now, let the chaos begin.
As I stated before we can only use constants and recursion no variables or loops.
1 let’s start with the initial function that we will call. It will just need a check to make sure the array has more than 1 object in it. Then call a function to recursively go through the values if it has more than 1 object. That function will look something like this.
2 In the parameters for the next function you can see we call sorted which will be the sorted array, unsorted which will be the initial array, and order which itself is a function, actually we call it a higher order function we will get into that later. Inside the next function we will continue to call itself until the unsorted array is empty. It will also need to generate the sorted array and the unsorted array. The sorted array on the first step will just be the first element all alone. But, on all steps after that it will be the sorted array plus the next value at the correct index (which will require another function). The unsorted array will just always be itself minus the first value. The next function should look something like this.
4 Lastly, we will need a function that calculates the correct index to place the value in. This function will need to know what kind of order we are going in, what value is being inserted, and what values have we already checked (what index are we on). Inside that function we will check to make sure we are above index zero. If we are at zero we will need to know to place the value at the start of the array (index zero) or as the second element of the array. If we are not at index zero then we will check to see if the element is above or beneath the value at the current index. If it is what we are looking for (this depends if we are going ascending or descending) then we will place it in the array where it belongs. If it ins’t above or below what we are looking for then we will call the function again.
That’s it for insertion sort. For all of the code you can find it here. Also, if you are looking a swift developer feel free to reach out to me.