Ranks are relative to the current segment. The pivot's rank is The array partitioning places exactly
p-l, not its absolute index:def select(k: Int, l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
require(0 <= k && k < r - l)
if (r - l == 1) a(l)
else {
val p = partition(l, r)
val rank = p - l
if (k == rank) a(p)
else if (k < rank) select(k, l, p)
else select(k - rank - 1, p + 1, r)
}
}rank strictly smaller entries before the pivot, with all later entries at least the pivot. Thus the pivot is the element of sorted rank rank, even when equal values occur later. A requested earlier rank is unchanged in the left segment; a later rank loses the low entries and the pivot, accounting for the subtraction rank+1. The recursive segment is nonempty in either branch that takes it, and its length strictly decreases. Induction on segment length therefore proves the returned value is the requested order statistic, with at most one recursive call. Only the selected segment is permuted; all outside entries remain unchanged. This is Quickselect. Articles by others on the same topic
There are currently no matching articles.