Randomized Algorithms and Fisher-Yates

Why Randomization Helps

Randomization is useful because it breaks patterns you do not control. If an input distribution is adversarial, a deterministic rule may repeatedly choose the worst possible path through an algorithm. A randomized rule spreads that risk out so no single bad input layout can reliably force the same disaster every time. In interviews, this usually appears as expected-time guarantees for quicksort, quickselect, hash-based structures, and sampling. In systems, the same principle shows up in load balancing, retry jitter, backoff strategies, and fairness mechanisms.

The important phrase is expected behavior. Randomized algorithms do not promise that every run is perfect. They promise that, averaged over the algorithm’s own random choices, the bad runs become sufficiently rare or sufficiently limited. That is often exactly what you need. If a pivot choice is random, the chance of picking terrible pivots over and over is small. If a shuffle is truly uniform, every permutation is equally likely, so you are not biasing your test data, game mechanics, or sampling pipeline.

Why Naive Shuffling Is Biased

A surprisingly common mistake is to shuffle an array by looping over each index i and swapping it with a uniformly random index chosen from the entire array. That feels plausible because lots of swaps happen, but it does not produce all permutations with equal probability. Some arrangements can be reached through more swap sequences than others, so they end up overweighted. When correctness depends on fairness, “looks random enough” is not good enough.

For a 3-element array [A, B, C], the naive method makes 3 independent random choices, each with 3 options, for a total of 27 equally likely swap sequences. But there are only 6 possible final permutations. Because 27 is not a multiple of 6, those permutations cannot all receive the same number of sequences. Some outcomes must be more common than others. That counting argument alone proves bias, even before you enumerate the exact frequencies.

Fisher–Yates Shuffle

Fisher–Yates fixes the bias by shrinking the choice set as the algorithm progresses. Start at the end of the array. Pick a random index j between 0 and i inclusive, swap positions i and j, then move one step left. After that swap, position i is final and will never be touched again. On the next iteration you choose uniformly among the remaining unfixed elements. This ensures that every element gets exactly one fair chance to land in each position.

Walk through [7, 11, 13, 17]. For i = 3, suppose j = 1. Swap to get [7, 17, 13, 11]; now 11 is fixed at the end. For i = 2, suppose j = 0. Swap to get [13, 17, 7, 11]; now 7 is fixed in position 2. For i = 1, suppose j = 1, so the prefix stays [13, 17]. The final array is [13, 17, 7, 11]. At each step the algorithm chose uniformly from exactly the elements that had not yet been assigned a final slot.

Why is it uniform? Think position by position. Any element has probability 1/n of being chosen for the last slot. Conditional on that decision, any remaining element has probability 1/(n-1) of being chosen for the next slot, and so on. Multiply those probabilities and every full permutation receives the same value: 1/n!. That simple product argument is the reason Fisher–Yates is the standard shuffle in serious software instead of ad-hoc repeated swapping.

Randomized Pivots and Expected Time

Shuffling is the cleanest randomization example, but the same design idea powers randomized quicksort and quickselect. Those algorithms are fast when the pivot tends to split the data reasonably well. A deterministic pivot rule can be attacked by already sorted or adversarially arranged data. A random pivot makes the bad split pattern unlikely to repeat many times. You are not improving the worst-case bound on paper, but you are making worst-case behavior much harder for the input to force consistently.

This is a good lesson in engineering trade-offs. Randomization is not an excuse to ignore proofs. You still need to argue what distribution the algorithm produces or what expected running time it achieves. But once the proof is in place, random choices can turn a fragile deterministic heuristic into a robust practical algorithm.

In other words, randomization is valuable precisely when it is disciplined. You are not sprinkling entropy on a broken algorithm and hoping it improves. You are choosing a probability distribution that removes structural bias or makes bad input arrangements unlikely to keep hurting you repeatedly. That mindset is what separates a sound randomized algorithm from an unreliable “it seemed random when I tested it” implementation.

Go Implementation

The Go example below focuses on Fisher–Yates, then adds a tiny randomized quickselect helper to show the broader pattern. Notice that the random generator is created once and passed around; reseeding on every call usually makes code worse, not better.

Sampling and Related Patterns

Once you trust randomization as a design tool, many interview questions become easier to categorize. Random Pick Index uses reservoir sampling ideas so every matching index stays equally likely even in a stream. Random Pick with Weight turns weights into a prefix-sum distribution and then samples a random target position. These are different implementations, but the same principle applies: define the probability you want first, then design the algorithm so each outcome receives exactly that probability mass.

That “probability first” habit is the safest way to debug random algorithms. If your method cannot clearly explain why one outcome has probability 1/n!, or w_i/sum(w), or 1/k among k matches, the implementation is probably flawed. With deterministic algorithms we often trace exact states; with randomized ones we also need to trace the distribution each step creates.

Practice Problems

Quiz

Summary

• Randomization helps by breaking deterministic patterns that adversarial inputs can exploit.
• A shuffle is only correct if the output distribution is uniform, not merely “random-looking.”
• Fisher–Yates achieves uniform shuffling by fixing one position at a time from a shrinking pool.
• Randomized pivot selection gives quicksort and quickselect strong expected behavior.
• Sampling problems should be designed from the target probability distribution backward.