Swift sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort

sorting algorithms.swift

//: Swift sorting algorithms

//: Bubble Sort

func bubbleSort(list : [Int]) -> [Int] {
    
    var list = list
    let listCount = list.count
    
    for oputer in (2..<listCount).reverse() {
        for inner in 0 ... outer - 1 {
            if list[inner] > list[inner+1] {
                let temp = list[inner]
                list[inner] = list[inner+1]
                list[inner+1] = temp
            }
        }
    }
    
    return list
}

//: Selection Sort

func selectionSort(list : [Int]) -> [Int] {
    
    var list = list
    var min = 0
    for outer in 0 ... list.count - 2 {
        min = outer
        for inner in outer + 1 ... list.count - 1 {
            if list[inner] < list[min] {
                min = inner
            }
        }
        
        let temp = list[outer]
        list[outer] = list[min]
        list[min] = temp
    }
    
    return list
}

//: Insertion Sort

func insertionSort(list : [Int]) -> [Int] {
    
    var list = list
    
    var temp = list.first!
    var inner = -1
    
    for outer in 1 ... list.count - 1 {
        temp = list[outer]
        inner = outer
        while inner > 0 && list[inner - 1] >= temp {
            list[inner] = list[inner - 1]
            inner -= 1
        }
        
        list[inner] = temp
    }
    return list
}

//: Merge Sort

func mergeSort(list : [Int]) -> [Int] {
    func merge(left leftRaw : [Int], right rightRaw: [Int] ) -> [Int] {
        
        var result = [Int]()
        
        var left = leftRaw
        var right = rightRaw

        var leftLength = left.count
        var rightLength = right.count
        
        while leftLength > 0 || rightLength > 0 {
            if leftLength > 0 && rightLength > 0 {
                if left.first < right.first {
                    result.append(left.first!)
                    left.removeFirst()
                    leftLength -= 1
                } else if right.first <= left.first {
                    result.append(right.first!)
                    right.removeFirst()
                    rightLength -= 1
                }
            } else if leftLength > 0  {
                result.append(left.first!)
                left.removeFirst()
                leftLength -= 1
            } else if rightLength > 0 {
                result.append(right.first!)
                right.removeFirst()
                rightLength -= 1
            }
        }
        
        return result
        
    }
    let length = list.count
    if length <= 1 {
        return list
    }
    let q = Int( floor(Double(length) / 2))
    let left = mergeSort( list[0..<q].map {  return $0 } )
    let right = mergeSort( list[q..<list.count].map {  return $0 } )
    return merge(left: left, right: right)
}

//: Quick Sort

func quickSort(list : [Int]) -> [Int] {
    
    if list.count == 0 {
        return []
    }
    
    var lesser = [Int]()
    var greater = [Int]()
    let pivot = list.first
    
    for i  in 1 ..< list.count {
        if list[i] < pivot {
            lesser.append(list[i])
        } else {
            greater.append(list[i])
        }
    }
    
    var sortedArray = quickSort(lesser)
    sortedArray.appendContentsOf( [pivot!] )
    sortedArray.appendContentsOf( quickSort(greater) )
    
    return sortedArray
}