Pattern Reference
Randomized Algorithms
"Randomized quickselect, reservoir sampling, Fisher-Yates shuffle, Monte Carlo methods, Miller-Rabin."
Loading...
Deep Dive Tutorial
Randomized algorithms exchange deterministic guarantees for expected-case guarantees. The classic example: QuickSort with fixed pivot is O(n²) on sorted input — with random pivot, expected O(n log n) regardless of input. Reservoir sampling solves "pick k uniform random items from a stream of unknown length" elegantly: keep k items, each new item i replaces a random previous item with probability k/i.
Core randomized algorithm templates
// Reservoir sampling — pick k items uniformly at random from stream
function reservoirSample(stream, k) {
const reservoir = stream.slice(0, k);
for (let i = k; i < stream.length; i++) {
const j = Math.floor(Math.random() * (i + 1)); // random in [0, i]
if (j < k) reservoir[j] = stream[i]; // replace with probability k/(i+1)
}
return reservoir;
}
// Fisher-Yates shuffle — O(n), uniform random permutation
function shuffle(arr) {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
// Randomized QuickSelect — O(n) expected k-th smallest
function quickSelect(arr, k) { // k is 1-indexed
const pivot = arr[Math.floor(Math.random() * arr.length)];
const lo = arr.filter(x => x < pivot);
const mid = arr.filter(x => x === pivot);
const hi = arr.filter(x => x > pivot);
if (k <= lo.length) return quickSelect(lo, k);
if (k <= lo.length + mid.length) return pivot;
return quickSelect(hi, k - lo.length - mid.length);
}Worked Problems
dices
Reservoir sampling proof: After processing n items with k=1, item at position i was kept iff it replaced the previous choice AND no subsequent item replaced it. Probability = (1/i) * (i/(i+1)) * ((i+1)/(i+2)) * ... * ((n-1)/n) = 1/n. ✓
When to randomize:
- QuickSort/QuickSelect on unknown input (avoid O(n²) worst case)
- Sampling from stream without knowing length
- Hashing (random hash functions avoid collisions)
- Testing / approximation algorithms
Fisher-Yates correctness: Each of n! permutations is equally likely. After k iterations, the last k elements form a uniform random k-permutation.
When to randomize:
- QuickSort/QuickSelect on unknown input (avoid O(n²) worst case)
- Sampling from stream without knowing length
- Hashing (random hash functions avoid collisions)
- Testing / approximation algorithms
Fisher-Yates correctness: Each of n! permutations is equally likely. After k iterations, the last k elements form a uniform random k-permutation.