What
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the “average case” over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.
Fisher–Yates Shuffle
Fisher–Yates shuffle - Wikipedia
The Original Method
- Pick a random number k between one and the number of unstruck numbers remaining (inclusive). (Choose an unused number)
- Counting from the low end, strike out the k th number not yet struck out, and write it down at the end of a separate list. (Shuffle it)
- Repeat from step 2 until all the numbers have been struck out. (Get result)
Knuth Method
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
Las Vegas Algorithm
Las Vegas algorithm - Wikipedia
It always gives correct results; that is, it always produces the correct result or it informs about the failure.