Implementing Insertion Sort Fast AF

Insertion sort is a simple and efficient sorting algorithm that works by iterating through an array and inserting each element into its proper place in the sorted portion of the array. This is done by comparing the element to its neighbors and shifting them as necessary to make room for the element being inserted.

In this tutorial, we will learn how to implement insertion sort in Swift and understand how it works by walking through an example.

Implementation:

To implement insertion sort in Swift, we will create a function that takes an array of integers as an argument and returns a sorted version of that array.

Here is the code for our insertion sort function:

func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array
    for i in 1..<sortedArray.count {
        let current = sortedArray[i]
        var j = i - 1
        while j >= 0 && sortedArray[j] > current {
            sortedArray[j+1] = sortedArray[j]
            j -= 1
        }
        sortedArray[j+1] = current
    }
    return sortedArray
}

Now let’s break down how this function works.

First, we create a mutable copy of the input array and assign it to a variable called sortedArray. This is because we will be modifying the array as we sort it, and we don't want to modify the original input array.

Next, we have a for loop that iterates through all the elements of the array, starting from the second element (index 1). For each iteration, we assign the current element to a variable called current and assign the index of the previous element to a variable called j.

Inside the for loop, we have a while loop that continues as long as j is greater than or equal to 0 and the element at index j is greater than current. This while loop shifts the elements to the right to make room for the element being inserted.

Finally, outside the while loop, we insert the element being considered (current) into its proper place by assigning it to the index j+1.

Example:

Let’s walk through an example to see how insertion sort works on a small array.

Suppose we have the following array: [5, 2, 4, 1, 3]

The first element (5) is already sorted, so we move on to the second element (2). We compare 2 to its neighbors (5 and 4) and find that it is smaller than both of them. We shift 5 and 4 to the right to make room for 2, resulting in the following array: [2, 5, 4, 1, 3]

Next, we move on to the third element (4). We compare 4 to its neighbors (5 and 2) and find that it is larger than 2 but smaller than 5. We shift 5 to the right to make room for 4, resulting in the following array: [2, 4, 5, 1, 3]

We continue this process until we reach the final element (3). We compare 3 to its neighbors (1 and 5) and find that it is larger than 1 but smaller than 5. We shift 5 to the right to make room for 3, resulting in the following array: [1, 2, 3, 4, 5]

At this point, the array is fully sorted and the function returns the sorted array: [1, 2, 3, 4, 5]

Conclusion:

In conclusion, insertion sort is a simple yet efficient sorting algorithm that works by iterating through an array and inserting each element into its proper place in the sorted portion of the array. It is a useful algorithm for sorting small arrays or for sorting arrays that are already partially sorted.

For more information on insertion sort and other sorting algorithms, you can refer to the Swift documentation on sorting and the Wikipedia page on sorting algorithms.

I hope this tutorial has been helpful in understanding how to implement insertion sort in Swift and how it works. Happy coding!