selection rank

kth smallest element (element with rank k) in an array.
Or k smallest elements in an array.

// time: O(n)
x selectionRank(a, rank):
    // rank is 0 based
    if a == null || !(0 <= rank < a.length()):
        throw
    return selectionRankInner(a, rank)

x selectionRankInner(a, rank, start = 0, end = a.length() -1):
    pivot, pivotindex = (a, start, end)
    if rank < pivotindex:
        return selectionRankInner(a, rank, start, pivotindex-1)
    else if rank > pivotindex:
        return selectionRankInner(a, rank, pivotindex+1, end)
    return pivot

(pivot, pivotindex) partition(a, start, end):
    // validations
    if a == null || start > end || start < 0 || end >= a.length():
        throw
    pivotindex = random(start, end) //start, end inclusive
    pivot = a[pivotindex]
    swap(a, pivotindex, end)
    lo = start
    hi = end -1
    while lo <= hi:
        if a[lo] <= pivot:
            lo++
        else:
            swap(a, lo, hi)
            hi--
    pivotindex = lo // pivotindex is lo = hi +1
    swap(a, pivotindex, end)
    return (pivot, pivotindex)

[Hat tip to ctci]