BasicSorts.swift

// Insertion Sort

func insertionSort(_ elements: [Int]) -> [Int] {
    guard elements.count >= 2, let last = elements.last else { return elements }
    
    var copy = elements
    var pivot = last
    var idx: Int
    for index in 0..<(elements.count - 1) {
        idx = index
        pivot = copy[idx + 1]
        while (idx >= 0) && copy[idx] > pivot {
            copy[idx + 1] = copy[idx]
            idx -= 1
        }   
        copy[idx + 1] = pivot
    }
    return copy
}

// Selection Sort

func selectionSort(_ items: [Int]) -> [Int] {
    var copy = items
    for index in (0..<items.count) {
        var minEleIndex = index
        for idx in ((index+1)..<items.count) {
            if copy[idx] < copy[minEleIndex] {
                minEleIndex = idx
            }
        }
        copy.swapAt(minEleIndex, index)
    }
    return copy
}

// Counting Sort

func countingSrt(_ elements: [Int]) -> [Int] {
    guard let max = elements.max() else { return elements}
    
    var counts = [Int].init(repeating: 0, count: max + 1)
    for item in elements {
        counts[item] += 1
    }
    
    // construct output array
    var cpy = elements
    var itr = 0
    for (index, item) in counts.enumerated() {
        print("Index: \(index) item: \(item)")
        for _ in 0..<item {
            cpy[itr] = index
            itr += 1
        }
    }
    return cpy
}


// BROKEN

func partition(_ elements: inout [Int], low: Int, high: Int) -> Int {
    guard low < high else { return low }
    
    let pivot = elements[high]
    print("Pivot: \(pivot)")
    var store = low - 1
    
    for index in (low...high) {
        if elements[index] <= pivot {
            store += 1
            elements.swapAt(store, index)
        }
    }
    
    elements.swapAt(store + 1, high)
    return store
}


func quickSort(_ elements: inout [Int], low: Int, high: Int) {
    
    guard low < high else { return }
    
    let pi = partition(&elements, low: low, high: high)
    
    quickSort(&elements, low: low, high: pi-1)
    quickSort(&elements, low: pi+1, high: high)
}