Quick Sort


func partition(arr: inout [Int], front: Int, end: Int) -> Int {
    let pivot = arr[end]
    var i = front - 1
    for j in front ..< end {
        if arr[j] < pivot {
            i += 1
            arr.swapAt(i, j)
        }
    }
    i += 1
    arr.swapAt(i, end)
    return i
}

func quickSort(arr: inout [Int], front: Int, end: Int) {
    if front < end {
        let pivot = partition(arr: &arr, front: front, end: end)
        quickSort(arr: &arr, front: front, end: pivot - 1)
        quickSort(arr: &arr, front: pivot + 1, end: end)
    }
}


var arr = [4,3,2,1]
quickSort(arr: &arr, front: 0, end: 3)
print(arr)

Time complexity:

Best case: O(nlogn)

Average case: O(nlogn)

Worst case: O(n^2)

Ref: https://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html