Replace the tail call by updates to local bounds and a local rank:The loop invariant says that , , and selecting rank
def selectIterative(k: Int, l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
require(0 <= k && k < r - l)
var low = l
var high = r
var rank = k
while (high - low > 1) {
val p = partition(low, high)
val pivotRank = p - low
if (rank == pivotRank) return a(p)
if (rank < pivotRank) high = p
else {
rank -= pivotRank + 1
low = p + 1
}
}
a(low)
}rank in the active segment yields the originally requested order statistic. The original segment's multiset is preserved, and outside it no entries change. The updates are exactly the recursive reductions proved in part (c). The loop variant is ; a non-returning iteration strictly decreases it. A one-entry segment has only rank zero, establishing the final return. Auxiliary space is , rather than a potentially deep call stack. Articles by others on the same topic
There are currently no matching articles.