Compare values directly, avoiding subtraction that could overflow:Each branch returns an index whose value lies between the other two sampled values. Non-strict comparisons make ties harmless. The precondition is a nonempty valid segment, not a segment of at least three elements: for lengths one or two some sample indices coincide, but the code still returns a valid median of the sampled triple. This matters because selection can reach a two-element segment. With three distinct sample values, the pivot is not the minimum or maximum of the whole segment, but it need not be near the segment's true median. Median-of-three pivot selection is a heuristic, not a balance guarantee.
def bestIndex(l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
val first = l
val middle = l + (r - l) / 2
val last = r - 1
if (a(first) <= a(middle)) {
if (a(middle) <= a(last)) middle
else if (a(first) <= a(last)) last
else first
} else {
if (a(first) <= a(last)) first
else if (a(middle) <= a(last)) last
else middle
}
}Set aside the selected pivot at the end, array partitioning the other entries, then move the pivot to the separation index:The loop invariant is , , , and . The segment's multiset is unchanged and all entries outside it are unchanged. A low entry is swapped into the low segment; a high entry simply extends the high segment. The loop variant is . At exit, exchanging the reserved pivot with
def partition(l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
def swap(i: Int, j: Int): Unit = {
val t = a(i); a(i) = a(j); a(j) = t
}
val chosen = bestIndex(l, r)
val x = a(chosen)
swap(chosen, r - 1)
var p = l
var j = l
while (j < r - 1) {
if (a(j) < x) {
swap(p, j)
p += 1
}
j += 1
}
swap(p, r - 1)
p
}a(p) gives , , and . The displaced value at the old pivot position was already at least . Length one is handled by self-swaps and an empty loop. Duplicate pivot values belong to the high side. This costs time and auxiliary space.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.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.Test singleton and two-element segments, first/last/interior requested ranks, nonzero segment offsets, already sorted and reversed inputs, random inputs, all-equal inputs and several patterns of duplicates. Include
Int.MinValue and Int.MaxValue to expose overflow-prone comparisons. An independent sorted copy supplies the value oracle; also check preservation of the segment's multiset and of all outside entries. For speed tests, increase segment size and include deliberately unfavorable pivot arrangements, rather than timing random inputs alone.Distinct entries do not guarantee linear worst-case time: the worst case is . A median of three can repeatedly be the second-smallest remaining value, leaving a segment of size when seeking its maximum. The quadratic median-of-three selection family gives explicit distinct inputs realizing this behavior for the implementation above; one six-entry member is . Its recurrence is , yielding a quadratic sum. Balanced reductions instead give . Randomized or suitable average-case analyses give expected linear selection, but this deterministic heuristic alone supplies no such worst-case guarantee. Unlike Quicksort, Quickselect explores only one side, so a balanced run is linear rather than .
Articles by others on the same topic
There are currently no matching articles.