Swift implementation of popular sorting algorithms

sorting_algorithms_in_swift.swift

import Foundation

//popular sorting algorithms in swift


//Insertion Sort
//Complexity - Best O(n) - Average O(n2)
//We will perform comparing adjacent elements in the array for array length times
func InsertionSort<T: Comparable>(var list:[T]) -> [T] {
    for i in 1..<list.count {
        var j = i
        
        while j > 0 && list[j] < list[j-1] {
            let temp = list[j]
            list[j] = list[j-1]
            list[j-1] = temp
            
            j--
        }
    }
    return list
}


InsertionSort([4, 5, 67, -2, -2, 23, 45, 73, 21])
InsertionSort(["james", "sam", "zebra"])

//Bubble Sort
//Complexity - Best O(n) - Average O(n2)
func BubbleSort<T: Comparable>(var list:[T]) -> [T] {
    while (true) {
        var swapped = false
        for var i=1,j=i-1; i<count(list); i++, j++ {
            if list[j] > list[i] {
                let temp = list[j]
                list[j] = list[i]
                list[i] = temp
                swapped = true
            }
        }
        
        if !swapped {
            break
        }
    }
    return list
}

BubbleSort([4, 5, 67, 4, -2, 23, 45, 73, 21])
BubbleSort(["james", "sam", "zebra"])

//Selection Sort
//Complexity - Best O(n2) - Average O(n2)
//We will place the the max element in the last index, then move to the subset of the array leaving the last index as is

func SelectionSort<T: Comparable>(var list:[T]) -> [T] {
    for var i=0; i < list.count - 1; i++ {
        var j = list.count - (i + 1)
        var maxIdx = 0
        
        for k in 1...j {
            if list[maxIdx] < list[k]{
                maxIdx = k
            }
        }
        
        let temp = list[j]
        list[j] = list[maxIdx]
        list[maxIdx] = temp
    }
    return list
}

SelectionSort([4, 5, 5, 67, -2, 23, 45, 73, 1, Int.max, Int.min])
SelectionSort(["james", "sam", "zebra"])

//Mergesort
//Complexity - Best O(nlogn) - Average O(nlogn) - worst  O(nlogn)
func Merge<T: Comparable>(left:[T], right:[T]) -> [T] {
    var merged:[T] = []
    
    let lIdx = left.count-1
    let rIdx = right.count-1
    
    var i = 0
    var j = 0
    
    while i <= lIdx && j <= rIdx {
        if left[i] <= right[j] {
            merged.append(left[i])
            i++
        } else {
            merged.append(right[j])
            j++
        }
    }
    
    while i <= lIdx {
        merged.append(left[i])
        i++
    }
    
    
    while j <= rIdx {
        merged.append(right[j])
        j++
    }
    
    return merged
}

func MergeSort<T: Comparable>(var list:[T]) -> [T] {
    
    if list.count > 1 {
        //divide
        let midIdx = Int((list.count-1)/2)
        
        var left:[T] = Array(list[0...midIdx])
        var right:[T] = Array(list[midIdx+1...list.count-1])
        
        //recursive conquer
        list = Merge(MergeSort(left), MergeSort(right))
        
    }
    
    return list
}

MergeSort([4, 5, 5, 67, -2, 23, 45, 73, 1, Int.max, Int.min])
MergeSort(["james", "sam", "zebra"])

func PartitionIndex<T: Comparable>(inout list:[T], start: Int, end: Int) -> Int {
    var pivot = list[end]
    var wall = start
    
    for var i = start; i < end; i++ {
        if list[i] <= pivot {
            var temp = list[wall]
            list[wall] = list[i]
            list[i] = temp
            wall++
        }
    }
    
    var temp = list[wall]
    list[wall] = list[end]
    list[end] = temp
    
    return wall
}

//Quick Sort
//Complexity - Best O(n) - Average O(nlogn) - worst O(n2)
func QuickSort<T: Comparable>(inout list:[T], start: Int, end: Int) -> [T] {
    if start < end {
        var pidx = PartitionIndex(&list, start, end)
        QuickSort(&list, start,  pidx - 1)
        QuickSort(&list, pidx + 1, end)
    }
    
    return list
}

var narray = [4, 5, 5, 67, -2, 23, 45, 73, 1, Int.max, Int.min]
QuickSort(&narray, 0, count(narray) - 1)

The data structures used in these can be improved using swift specific types like tupples.

Please correct me if i'm wrong