Thursday, June 11, 2015

selection rank

kth smallest element (element with rank k) in an array.
// time: O(n)
selection-rank(a, rank, left = 0, right = a.length-1):
    if left > right:
        throw
    first = left
    last = right
    pivotindex = random(left, right) //left, right inclusive
    pivot = a[pivotindex]
    swap(a, pivotindex, last)
    right--
    while left <= right:
        if a[left] <= pivot:
            left++
        else:
            swap(a, left, right)
            right--
    pivotindex = left // right + 1 = left = pivotindex
    swap(a, pivotindex, last)
    if rank < pivotindex:
        return selection-rank(a, rank, first, pivotindex-1)
    else if rank > pivotindex:
        return selection-rank(a, rank, pivotindex+1, last)
    return max(a, first, pivotindex)

[Hat tip to ctci]

No comments:

Post a Comment