Shuffling Algorithms

Permute By Sorting §

Permute by Sorting. Image taken from CLRS

• (CLRS Lemma 5.4) Assuming all priorities are distinct, then the input is randomly permuted.

Fisher-Yates §

Fisher Yates Algorithm. Image taken from CLRS

• (CLRS Lemma 5.5). This algorithm produces a uniform random permutation.

  This holds because of the following following loop invariant:

  Just prior to the -th iteration of the loop, for each possible -permutation of the elements, the subarray contains with probability

Links §

• CLRS