= Solution
Ranks are relative to the current segment. The pivot's rank is `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)
}
}
``
The <array partitioning> places exactly `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 \b[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>.
Back to article page
