Skip to main content

Understanding the Knuth Shuffle Algorithm

Knuth Shuffle​

  • In iteration i, pick integer r between 0 and i uniformly at random.
  • Swap a[i] and a[r]
  • Proposition - Knuth shuffling algorithm produces a uniformly random permutation of the input array in linear time