Selection Sort Algorithms in Swift

1. Introduction

Selection Sort is a simple and intuitive sorting algorithm that works by dividing the input list into a sorted and an unsorted region, and repeatedly picking the smallest (or largest, depending on the sorting order) element from the unsorted region and moving it to the end of the sorted region.

2. Implementation Steps

1. Start with the first element of the list as the minimal.

2. Traverse the list to find the smallest element.

3. Swap the found smallest element with the first element.

4. Move to the next element and repeat the process until the entire list is sorted.

3. Implementation in Swift

func selectionSort<T: Comparable>(_ array: inout [T]) {
    let n = array.count
    for i in 0..<n {
        var minIndex = i
        // 2. Traverse the list to find the smallest element
        for j in (i+1)..<n {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        // 3. Swap the found smallest element with the first element
        array.swapAt(i, minIndex)
    }
}
// Example Usage
var numbers = [64, 25, 12, 22, 11]
selectionSort(&numbers)

Output:

The sorted array will be: [11, 12, 22, 25, 64]

Explanation:

1. Selection Sort starts by initializing the first element of the list as the minimal.

2. It then traverses the remaining list to find the element that is smallest compared to the initialized minimal.

3. Once the smallest element is found, it gets swapped with the first unsorted element.

4. The boundary between the sorted and unsorted region then moves one step to the right, and the process is repeated until the entire list is sorted.

The primary advantage of the Selection Sort is its simplicity and its performance characteristics. The algorithm performs O(n^2) comparisons but always performs O(n) swaps. This means that in scenarios where write or swap operations are costly, Selection Sort might outperform other algorithms that involve more swaps.