Shuffling Algorithm - Knuth Algorithm

You must be familiar how we shuffle a deck of card before start of any game. Its easy in real life to shuffle the deck of cards with hand.

How about in the online games? How would we shuffle a deck of card?

Shuffling should be done such that all the cards must be distributed uniformly i.e. every card should be distributed across the positions with equal probability. For the case of n items, all the items should be distributed with the probability of ${1 \over N}$.

Algorithm

1. We start by initializing $position = 0$.
2. Randomly pick an item from the array, range of the selection being $[position, N]$, where N = size of the array.
3. Swap the position of this random item with the item in the location $position$.
4. Increase $position$ by 1 and repeat from step 2 until $position == N$

Following this algorithm, it can be guaranteed that that each of the items in the array is uniformly distributed across the array with the probability of ${1 \over n}$.

$\def\specialFrac#1#2{\frac{x + #1}{y + #2}}$
• Probability of first item = $1 \over N$
• Probability of second item = \(\textrm{probability of not being selected for first time} \times \textrm{probability of getting selected out of (N-1) items}\) = $\frac {N-1}{N} \times \frac {1}{N-1}$ = $\frac {1}{N}$
• Probability of third item = \(\textrm{probability of not being selected for first time} \times \textrm{probability of not being selected for second time} \times \) \(\textrm{probability of getting selected out of (N-2) items}\) = $\frac {N-1}{N} \times \frac {N-2}{N-1} \times \frac {1}{N-2}$ = $\frac {1}{N}$
• and so on...

So we can see that the probability of \(\frac{1}{N}\) can be guaranteed for each of the items in the arra.

Implementation

Complexity

The algorithm shuffles the array in one pass and in place. So, the overall time complexity is $\cal{O(n)}$ and space complexity is $\cal{O(1)}$.

---

---

---