Quick Select - Find k-th item in an unsorted array.

1. Sort and find: O(nlogn)

2. Quick Select: O(n)

Quick Select: It is similar to Quick Sort about partitioning, but it does not need to sort all elements in an array. The most important thing is the location of pivot. If k, an index of the array, is less than an index of pivot, we need to care about only left part of k. We do not need to worry about a right side of pivot.

Ideal case: n + n/2 + n/4 + .... = n(1 + 1/2 + 1/4 + ....) = n ( 1 / (1 - 1/2) ) = 2n = O(n)

* Sn = a + ar + ar^2 + ar^3 + ... + ar^(n-2) + ar^(n-1) = a / (1 - r)

QuickSelect.groovy

def swap(list, a, b) {
    def temp = list[a]
    list[a] = list[b]
    list[b] = temp
}

def partition(list, pivot, left, right) {
    def storeIdx = left
    swap(list, pivot, right)

    for(int i = left; i < right; ++i) {
        if(list[i] < list[right]) {
            swap(list, i, storeIdx)
            storeIdx++
        }
    }
    swap(list, storeIdx, right)
    return storeIdx
}

def select(list, k, left, right) {
    while(true) {
        def pivot = new Random().nextInt(right - left +1) + left
        println "pivot = " + pivot

        def newPivot = partition(list, pivot, left, right)
        println list

        if(k == newPivot) {
            return list[k]
        } else if (newPivot < k) {
            left = newPivot + 1
        } else {
            right = newPivot - 1
        }
    }
}

def list = [9,8,7,4,5,0,2,1,6,3]
def left = 0
def right = list.size() - 1
def k = new Random().nextInt(right - left + 1 ) + left

println "k = " + k
println list

def answer = select(list, k, left, right)
println "[ANSWER] " + answer