233: Selection, Quickselect, Reservoir Sampling, and Randomized Algorithms

Learning outcomes

By the end of this lesson, you should be able to:

explain when quickselect is a better fit than sorting and apply it in a realistic implementation;
explain what pivot randomization changes, what it does not guarantee, and apply it deliberately;
explain how median of medians provides a deterministic selection guarantee and recognize its practical trade-offs;
explain and apply reservoir sampling when a stream has an unknown length;
implement and evaluate an unbiased random shuffle;
state the relevant invariant, edge cases, and complexity cost for each technique.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to choose a subset, find a rank, randomize an order, or process data that could not all be held in memory. The point is not to recite terminology. It is to make a defensible choice in both an interview-sized problem and a production data-processing problem.

Start with constraints: Is the input an in-memory array or a one-pass stream? Is the result required to be exact or merely random? Does the caller need a fully ordered result, one rank, or a fixed-size sample? Can the algorithm mutate the input? Those answers determine which technique is appropriate.

Terminology

Quickselect: A selection algorithm that partitions like quicksort, then recurses or iterates only into the partition containing the k-th element. Its expected runtime is O(n), while a sequence of poor pivots can produce O(n²) worst-case behavior.
Pivot randomization: Choosing a pivot randomly before partitioning. This makes an input order that is adversarial for a fixed pivot less likely to cause repeated unbalanced partitions. It changes the expected behavior, not the worst-case bound.
Median of medians: A deterministic pivot-selection algorithm. It groups values, finds each group's median, and selects a pivot from those medians. The pivot quality is sufficient to guarantee linear-time selection, although the extra work and larger constants often make it less attractive in ordinary interview or application code.
Reservoir sampling: A streaming method for maintaining k uniformly random samples when the stream length is unknown. After the reservoir is full, each incoming item gets a decreasing chance of replacing an existing sample.
Random shuffling: Fisher-Yates produces an unbiased permutation when the swap index is selected uniformly from the items that have not yet been fixed. Sorting by random keys is not a principled substitute: ties, biased key generation, and sorting behavior can distort the distribution.
Randomness contracts: Algorithmic randomness should usually be supplied by an injectable deterministic RNG or seedable source in tests. Cryptographic randomness has different security requirements and should not be treated as interchangeable with a convenient pseudo-random source.

Mental model

Treat Selection, Quickselect, Reservoir Sampling, and Randomized Algorithms as design problems with observable inputs, outputs, invariants, and failure modes. If the caller needs only the value at a rank, sorting every value may do unnecessary work. If the data arrives as a stream, sorting may not even be possible. Randomized algorithms can improve expected performance or provide an unbiased sample, but only when the random choice is made over the correct set of candidates.

For selection, the key mental model is “discard what cannot contain the answer.” Partitioning does not fully sort the array. It establishes a boundary around the pivot: values on one side are no greater or no smaller according to the chosen partition rule. Quickselect then continues only in the side that can still contain rank k. The invariant is about the candidate range, not about the entire array being ordered.

For sampling and shuffling, the invariant is probabilistic. A reservoir of size k must give every item seen so far the same probability of occupying each sample position. Fisher-Yates must choose uniformly from the remaining unfixed positions. This is where people usually get confused: “random-looking” output is not the same as a uniform distribution.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it, and decide how a test can observe a violation.

Deep dive

1. Quickselect

The problem is finding the k-th smallest or largest value without paying the full cost of sorting. Quickselect partitions the input as quicksort does, but it does not recursively process both sides. After partitioning around a pivot, it compares the pivot's final rank with k: if they match, the pivot is the answer; otherwise, it continues only in the side containing k.

The implementation needs a clear rank convention. For a zero-based k-th-smallest operation, k = 0 means the minimum and k = values.length - 1 means the maximum. Reject a missing, non-integer, or out-of-range rank before partitioning. Decide separately whether partitioning is allowed to mutate the caller's array. A copied working array is safer for callers, while in-place partitioning uses less additional storage.

The core invariant is that the discarded side cannot contain the requested rank. After each partition, retain the candidate interval and update its lower or upper bound. With a balanced pivot, the work is linear in expectation; with consistently extreme pivots, the work can become quadratic. Duplicates need an explicit partition policy, because a two-way partition can make an input containing many equal values progress slowly. A three-way partition separating less-than, equal-to, and greater-than values is often a better practical choice.

Decision rule: Use quickselect deliberately when a rank or top/bottom subset is required and the selection invariant is easier to preserve than a sort-based alternative. If the caller needs all values ordered, sorting is clearer. If the input is untrusted and a deterministic worst-case bound is required, consider median of medians or a trusted library implementation with a documented guarantee.

2. Pivot randomization

Quickselect's bad case is driven by pivot quality. A fixed rule such as “always choose the first element” behaves badly on already sorted input, reverse-sorted input, or input shaped to target that rule. Choosing the pivot index randomly breaks the connection between a known input ordering and the pivot rule, so repeated highly unbalanced partitions become unlikely under the RNG's assumptions.

Randomization is not a proof that every invocation is fast. A random sequence can still select poor pivots, and a biased or predictable generator can undermine the expected analysis. The useful distinction is between an expected O(n) runtime and a deterministic worst-case O(n) guarantee. Test the partition logic independently from the randomness, and inject the random source so a test can reproduce a failing sequence.

Decision rule: Use pivot randomization deliberately when expected linear performance is acceptable and the input may be adversarial to a fixed pivot rule. If latency must have a deterministic bound, randomization alone does not satisfy that contract. Also account for the operational cost of diagnosing rare bad runs: record enough context, such as input size and a reproducible seed where appropriate, without logging sensitive data.

3. Median of medians

When a worst-case linear-time selection guarantee matters, the pivot itself can be chosen more carefully. Median of medians divides the current range into small groups, finds each group's median, and recursively selects the median of those medians. That pivot is guaranteed to discard a constant fraction of the remaining elements, so the selection recurrence remains O(n) in the worst case.

The guarantee comes from pivot quality, not from sorting the whole input. Group size, handling of a final short group, rank conventions, and the partition implementation all need to be specified. The algorithm is more involved than randomized quickselect and generally has larger constants. In many application paths, a well-tested library or randomized approach is the more maintainable choice; median of medians is valuable when the deterministic guarantee is a stated requirement.

Decision rule: Use median of medians deliberately when the worst-case runtime is part of the contract, such as a tightly bounded service or an explicitly theoretical exercise. If the real requirement is simply “find a percentile efficiently” and occasional bad random choices are acceptable, its complexity may not justify the implementation burden.

4. Reservoir sampling

Suppose a stream is too large to store, its final length is unknown, and you need exactly k items chosen uniformly from the complete stream. Reservoir sampling keeps the first k items, then processes each later item at one-based position i. Select it with probability k / i; if selected, replace one of the k reservoir positions uniformly.

The invariant is that after processing i items, every item has probability k / i of being in the reservoir, assuming i >= k. The replacement probability is what preserves earlier items' chances: an existing item survives the new item only if the new item is not selected, or if it is selected but replaces a different slot. A common implementation mistake is to use a fixed replacement probability or to choose the replacement slot from the wrong range.

The contract must define what happens when k is zero, negative, larger than the number of items, or non-integral. For a finite stream, returning all available items when fewer than k arrive is one reasonable contract, but it must be documented; throwing an error is another. The algorithm uses O(k) storage and one pass, with O(1) expected work per item. It cannot provide a sample weighted by business value unless the selection probabilities are intentionally changed.

Decision rule: Use reservoir sampling deliberately when the source is one-pass or too large to retain and every item should have an equal chance of being selected. If the data is already in memory and must also be sorted or queried repeatedly, a direct in-memory approach may be simpler. For security-sensitive choices, use the randomness source required by the security contract, not whichever source is easiest to call.

5. Random shuffling

The requirement for a shuffle is stronger than “change the order.” Every permutation should be equally likely. Fisher-Yates meets that requirement by walking from the end of the array toward the beginning and choosing j uniformly from 0 through the current index i, then swapping positions i and j. Once position i is fixed, it is not touched again.

The invariant is that the suffix already processed is a uniformly random arrangement of the items that were selected for it, and the remaining prefix contains the unfixed items. The bounds on the random index matter. Choosing from the entire array on every iteration, using sort(() => Math.random() - 0.5), or excluding the current index can introduce bias. As with selection, decide whether to mutate the input and make that behavior part of the API contract.

Decision rule: Use random shuffling deliberately when each permutation needs equal probability. Use a seeded or injected RNG in tests so a particular sequence can be reproduced. A frequency experiment can reveal obvious bias, but a finite test cannot prove perfect uniformity; it is a diagnostic, not a mathematical proof.

6. Randomness contracts

Randomness is an input dependency, not a detail that should disappear inside the algorithm. The algorithm needs a source that can produce the required range without accidental modulo bias or an off-by-one error. Tests need control over that source so they can exercise replacement, non-replacement, each partition branch, and boundary indices deterministically.

Do not use ordinary pseudo-randomness for tokens, passwords, session identifiers, or other security-sensitive values. Conversely, using a cryptographic generator where a fast, reproducible algorithmic RNG is enough can make testing and performance needlessly difficult. Name the contract explicitly: uniform choice, reproducibility, unpredictability, or some combination.

Decision rule: Use randomness contracts deliberately when the algorithm's correctness or testability depends on random choices. If it only reduces typing while hiding an assumption, prefer the more explicit design.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence. For example: “Return the zero-based k-th smallest value without sorting the entire input.” Then list the input and output contracts: what counts as a valid array, whether k must be an integer, whether duplicates count as separate positions, whether the input may be mutated, and what an invalid request returns.

Identify which concept owns each failure mode. A rank lookup on an in-memory array may use quickselect. An unknown-length stream may require reservoir sampling instead. A request for a complete ordering is a sorting problem, not a quickselect problem. Parsing or validation belongs at the boundary; algorithmic invariants belong in the selection or sampling function; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but leaves edge cases harder to reason about.

The following small function is intentionally not a quickselect implementation. It demonstrates the habit of stating the invariant before choosing the data structure or algorithm. Its contract is incomplete because it does not define the empty-input case; a production version would need to do so explicitly.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this pure function, concurrency and dependency failure may not apply; say that rather than pretending every failure mode belongs here. For an algorithm, inspect the candidate range, pivot index, random bounds, and reservoir size. For each applicable case, state which layer detects the problem and what the caller observes. That is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For randomized algorithms, also ask whether the result must be reproducible, whether the RNG can be seeded, whether a rare bad partition can exceed a latency budget, and whether sampling bias would affect a business decision.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. A quickselect that saves sorting work but mutates a shared array can create a correctness bug. A reservoir that fits in memory but silently returns a biased sample can produce misleading analytics. A shuffle that looks random in a demo can still fail a fairness or allocation requirement.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and network input is untrusted. Randomized algorithm code does not remove any of those boundaries; it adds a probability contract that must be tested and monitored.

Guided lab

Implement quickselect for the k-th smallest value, Fisher-Yates shuffle, and reservoir sampling of k items from a stream. Decide and document rank indexing, invalid-input behavior, mutation behavior, and the behavior when a stream contains fewer than k items. Write a small frequency experiment that runs many shuffles and checks whether an intentionally wrong shuffle shows a visibly different distribution from Fisher-Yates.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing. For example, inspect partition bounds, replacement counts, and permutation frequencies.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the randomized parts, use an injectable deterministic RNG in ordinary unit tests. Keep distribution checks separate from branch and boundary tests: a frequency experiment can detect a likely bias, while deterministic tests verify exact control flow.

Edge cases and failure modes

Quickselect: Test absence of input, malformed input, a missing, fractional, negative, or out-of-range rank, duplicates, already sorted and reverse-sorted data, all-equal values, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the mutation contract and the largest credible recursion depth.
Pivot randomization: Test absence of an RNG, malformed random output, duplicate-heavy and adversarial orderings, reproducible seeds, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that the selected index is within the current partition bounds.
Median of medians: Test absence, malformed input, duplicates, groups smaller than the nominal group size, rank boundaries, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check that the deterministic guarantee is not accidentally lost through an incorrect partition.
Reservoir sampling: Test absence, malformed input, k = 0, negative or non-integral k, an empty stream, fewer than k items, exactly k items, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible stream sizes. Verify the O(k) memory bound and uniform replacement range.
Random shuffling: Test absence, malformed input, empty and one-item arrays, duplicates, repeated runs with a controlled RNG, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify that every swap index includes both endpoints required by Fisher-Yates.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. Sorting is not a substitute for selection when memory, latency, or mutation constraints say otherwise.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. A type annotation does not validate runtime input.
Testing only the happy path and therefore discovering rank, RNG, and stream contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Expected linear time does not automatically mean lower end-to-end latency.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Treating random-looking output as proof of uniformity, or using a random-key sort as a shuffle without understanding its distribution.

For debugging, reproduce the smallest failing case and, where possible, fix the RNG seed. Inspect the actual candidate interval, pivot and partition boundaries, random index range, reservoir contents, or permutation counts. Trace the boundary where the invariant first becomes false, then fix the owning layer rather than adding a downstream patch. If the issue is a rare performance failure, capture a safe reproducibility signal and measure the input size and partition behavior instead of guessing from the final result.

Interview questions

What problem does Quickselect solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Pivot randomization solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Median of medians solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Reservoir sampling solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Random shuffling solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Selection, Quickselect, Reservoir Sampling, and Randomized Algorithms to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be precise about which guarantee is deterministic and which is expected or probabilistic.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.