Randomized algorithms

A randomized algorithm uses random choices as part of how it works, usually to get something simple that’s fast on average no matter what input it gets. Quicksort with a random pivot is the classic case: an adversary can’t prepare an input that triggers its slow worst case, because the algorithm’s choices aren’t known in advance. Reservoir sampling picks a fair random item from a stream too long to store, using one pass and fixed memory. The Fisher–Yates shuffle produces every ordering with equal probability, which some intuitive-looking shuffles don’t. Randomness also shows up in hash seeds, skip lists, load balancing and quickselect, which finds the median in linear time on average.