single_pivot_qs.swift

func swap<T>(inout arr: [T], src: Int, dest: Int) {
    let tmp = arr[dest]
    arr[dest] = arr[src]
    arr[src] = tmp
}

func quicksort<T: Comparable>(inout arr: [T]) {
    if arr.count < 2 {
        return
    }
    
    quicksort(&arr, lo: arr.startIndex, hi: arr.endIndex.advancedBy(-1))
}

func quicksort<T: Comparable>(inout arr: [T], lo: Int, hi: Int) {
    if (lo >= hi) {
        return
    }
    
    let privotIndex = partition(&arr, lo: lo, hi: hi)
    
    quicksort(&arr, lo: lo, hi: privotIndex.advancedBy(-1)) // values < pivot 
    quicksort(&arr, lo: privotIndex.advancedBy(1), hi: hi) // values > pivot
}

func partition<T: Comparable>(inout arr: [T], lo: Int, hi: Int) -> Int {
    let pivot = arr[lo]
    var start = lo + 1 // except pivot
    var end = hi
    
    while start < end {
        if start < end && arr[start] < pivot { // skip values < pivot
            start = start.advancedBy(1)
        }
        
        if start < end && arr[end] > pivot { // skip values > pivot
            end = end.advancedBy(-1)
        }
        
        if start >= end {
            break
        }
        
        swap(&arr, src: start, dest: end)
    }
    
    swap(&arr, src: lo, dest: end) // move pivot value between values < pivot and values > pivot
    
    return end // return pivot index
}