Fisher-Yates shuffle, also known as Knuth shuffle, is an algorithm for generating a random permutation of a finite sequence. It efficiently shuffles an array, making each possible permutation equally likely.
The algorithm works by dividing the input array into two parts: a shuffled section and an unshuffled section. It repeatedly takes a random element from the unshuffled section and inserts it into the shuffled section, swapping the elements as needed.
- Start with the last element of the array.
- Swap the current element with a randomly selected element before it (including itself).
- Move to the previous element and repeat step 2.
- Continue this process until the first element of the array is reached.
| Case | Complexity |
|---|---|
| Worst | O(n) |
| Average | O(n) |
| Best | O(n) |
| Case | Complexity |
|---|---|
| Worst | O(1) |
| Average | O(1) |
| Best | O(1) |
The algorithm itself is unbiased, but the random number generator used to select the elements may not be. In this implementaion, since the Math.random() function from JavaScript is a pseudo-random number generator (PRNG), the algorithm isn't truly unbiased. However, the bias is so small that it can be ignored for most applications.