Randomization function

In computer science, randomization function or randomizing function is a algorithm or procedure that implements a random function between two specific sets.

Randomizing functions are central to the design of randomized algorithms, that have good expected performance for any input. For example, consider an algorithm like quicksort, which has small expected running time for random inputs, but is very slow when the input data are presented in certain unfavorable orders. A randomizing function from the integers 1 to n to the integers 1 to n can be used used to rerrange the n input items in "random" order, before calling that algorithm. This modified algorithm will have small expected running time for any input.

Randomizing functions are related to random number generators and hash functions, but have somewhat different requirements and uses, and often need specific algorithms.

{[stub}}