Deterministic Select

Deterministic Select finds the k-th smallest element with guaranteed linear time. It avoids bad pivot choices by constructing a pivot that ensures balanced partitioning.

This algorithm is often called the Blum-Floyd-Pratt-Rivest-Tarjan selection algorithm.

Problem

Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$ , return the k-th smallest element.

Algorithm

Divide the array into groups of five, find the median of each group, then recursively compute the median of those medians. Use that value as pivot.

deterministic_select(A, k):
    if length(A) <= 5:
        sort A
        return A[k]

    groups = split A into groups of 5
    medians = [median of each group]

    pivot = deterministic_select(medians, length(medians) // 2)

    L = [x in A where x < pivot]
    E = [x in A where x == pivot]
    R = [x in A where x > pivot]

    if k < length(L):
        return deterministic_select(L, k)
    else if k < length(L) + length(E):
        return pivot
    else:
        return deterministic_select(R, k - length(L) - length(E))

Key Idea

Grouping into size five guarantees that the pivot lies within a controlled rank range. At least a constant fraction of elements are discarded at each step, ensuring linear progress.

Correctness

Partitioning preserves order. The pivot is chosen from actual elements, so it has a valid rank. The recursion reduces the problem size while maintaining the target rank.

Complexity

case	time
worst	$O(n)$
best	$O(n)$
average	$O(n)$

The recurrence is:

T(n) = T(n/5) + T(7n/10) + O(n)

which solves to linear time.

Space:

O(1)

for in-place partitioning, ignoring recursion stack.

When to Use

Use Deterministic Select when:

worst-case guarantees are required
adversarial inputs are possible
predictable latency matters

In practice, Randomized Quickselect is faster due to smaller constants.

Implementation

def deterministic_select(a, k):
    if len(a) <= 5:
        return sorted(a)[k]

    groups = [a[i:i+5] for i in range(0, len(a), 5)]
    medians = [sorted(group)[len(group)//2] for group in groups]

    pivot = deterministic_select(medians, len(medians)//2)

    lows = [x for x in a if x < pivot]
    highs = [x for x in a if x > pivot]
    pivots = [x for x in a if x == pivot]

    if k < len(lows):
        return deterministic_select(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        return deterministic_select(highs, k - len(lows) - len(pivots))

func DeterministicSelect(a []int, k int) int {
	if len(a) <= 5 {
		tmp := make([]int, len(a))
		copy(tmp, a)
		sortInts(tmp)
		return tmp[k]
	}

	var medians []int
	for i := 0; i < len(a); i += 5 {
		end := i + 5
		if end > len(a) {
			end = len(a)
		}
		group := make([]int, end-i)
		copy(group, a[i:end])
		sortInts(group)
		medians = append(medians, group[len(group)/2])
	}

	pivot := DeterministicSelect(medians, len(medians)/2)

	var lows, highs, pivots []int
	for _, v := range a {
		if v < pivot {
			lows = append(lows, v)
		} else if v > pivot {
			highs = append(highs, v)
		} else {
			pivots = append(pivots, v)
		}
	}

	if k < len(lows) {
		return DeterministicSelect(lows, k)
	} else if k < len(lows)+len(pivots) {
		return pivot
	}
	return DeterministicSelect(highs, k-len(lows)-len(pivots))
}