Fisher-Yates Shuffle: The Right Way to Randomize an Array

How the Fisher-Yates Algorithm Randomly Shuffles an Array

The Fisher-Yates Shuffle (also known as the Knuth Shuffle) is a classic algorithm for randomly shuffling elements in an array. Unlike naive shuffling approaches, this algorithm produces an unbiased permutation, meaning that each possible ordering is equally likely.

In this article, we'll go over:

• A visual explanation of the algorithm
• JavaScript code implementation
• Time and space complexity

Visual Explanation

Here's how the Fisher-Yates algorithm works, visualized step-by-step:

Source: https://www.researchgate.net/figure/The-scrambling-process-of-Fisher-Yates-algorithm_fig1_350148237

The process works by iterating from the last element to the first and swapping each element with a randomly selected element that comes before it (including itself).

JavaScript Implementation

Here's how you can implement the Fisher-Yates algorithm in JavaScript:

function fisherYatesShuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    // Generate a random index j such that 0 ≤ j ≤ i
    const j = Math.floor(Math.random() * (i + 1));

    // Swap elements at indices i and j
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

// Example usage
const arr = [1, 2, 3, 4, 5, 6, 7];
console.log("Shuffled array:", fisherYatesShuffle(arr));

Time Complexity

• Best, Average, and Worst Case: ( O(n) ), where ( n ) is the number of elements in the array. The algorithm performs exactly ( n - 1 ) swaps.

Space Complexity

• In-place shuffle: ( O(1) ) auxiliary space. It modifies the original array without using any additional memory for copying or temporary arrays.

Why Fisher-Yates?

Many naive shuffle methods, such as sorting an array using a random comparator (e.g. arr.sort(() => Math.random() - 0.5)), are biased and do not produce uniform randomness. The Fisher-Yates algorithm is the gold standard for random shuffling in-place.

Now you know how to shuffle arrays like a pro! 🎲 If you enjoyed this explanation, feel free to leave a ❤️ or share your own shuffling use cases in the comments.

Happy coding!