Insertion Sort Algorithms in Swift

1. Introduction

Insertion Sort is a simple sorting algorithm that works similarly to how one sorts playing cards in their hands. It builds the final sorted array one item at a time. It's generally used when the number of elements is small or when the input array is almost sorted, and only a few elements are misplaced.

2. Implementation Steps

1. Start from the second element (assume the first element is sorted).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous element, compare it with the elements before until an element smaller than it is found or until the start of the array is reached.

4. Place the current element in its correct position so that the elements before are smaller than the current element.

5. Repeat the above steps for all the elements in the array.

3. Implementation in Swift

func insertionSort(_ array: inout [Int]) {
    for i in 1..<array.count {
        // 1. Start from the second element
        let key = array[i]
        var j = i - 1
        // 2. Compare the current element with the previous element
        while j >= 0 && array[j] > key {
            // 3. If current element is smaller, compare with elements before it
            array[j + 1] = array[j]
            j = j - 1
        }
        // 4. Place the current element in its correct position
        array[j + 1] = key
    }
}
// Usage:
var numbers = [64, 34, 25, 12, 22, 11, 90]
insertionSort(&numbers)
print(numbers)

Output:

[11, 12, 22, 25, 34, 64, 90]

Explanation:

1. We start by iterating from the second element of the list (assuming the first element is already sorted).

2. For each iteration, we store the current element in a variable key. We then compare this key with the previous elements.

3. If the key is smaller than the previous element, we shift the previous element to the right. We continue shifting elements until we find the correct position for the key or until we reach the start of the list.

4. We then place the key in its correct position such that elements to the left are smaller and elements to the right are larger.

5. This process is repeated for every element in the array, resulting in a sorted list at the end.