Implementing the Fisher-Yates Shuffle Algorithm in JavaScript

The Fisher-Yates shuffle (also known as the Knuth shuffle) is a widely used algorithm for randomly shuffling the elements of an array in place. This is a fundamental algorithm in computer science with applications in simulations, games, and any scenario requiring a random permutation of a dataset. Your task is to implement this algorithm in JavaScript.

Problem Description

You are required to implement a function called shuffleArray that takes an array as input and shuffles its elements randomly in place. The function should modify the original array directly and return the shuffled array. The shuffling should be done using the Fisher-Yates shuffle algorithm to ensure a uniform distribution of possible permutations.

Key Requirements:

• In-place modification: The function must modify the original array directly, without creating a new array.
• Uniform distribution: The shuffling algorithm should produce a uniform distribution of all possible permutations of the input array. This means each permutation should be equally likely.
• Correctness: The function should correctly shuffle arrays of any size, including empty arrays and arrays with duplicate elements.

Expected Behavior:

The shuffleArray function should take an array as input and return the same array, but with its elements rearranged in a random order. The order of elements in the returned array should be different each time the function is called with the same input array.

Edge Cases to Consider:

• Empty array: The function should handle an empty array gracefully without errors.
• Array with one element: The function should handle an array with only one element correctly (no change is needed).
• Array with duplicate elements: The function should still produce a valid shuffle even if the array contains duplicate elements.

Examples

Example 1:

Input: [1, 2, 3, 4, 5]
Output: [4, 1, 3, 5, 2]  // Example - the actual output will be different each time
Explanation: The array [1, 2, 3, 4, 5] is shuffled randomly, resulting in a different permutation.

Example 2:

Input: [1, 1, 2, 2]
Output: [2, 1, 2, 1] // Example - the actual output will be different each time
Explanation: The array [1, 1, 2, 2] is shuffled randomly, even with duplicate elements.

Example 3:

Input: []
Output: []
Explanation: An empty array remains empty after shuffling.

Constraints

• Input: The input will be an array of any data type (numbers, strings, objects, etc.).
• Array Size: The array can contain between 0 and 1000 elements.
• Performance: The algorithm should have a time complexity of O(n), where n is the number of elements in the array. Avoid unnecessary operations that could degrade performance.
• Randomness: Use Math.random() for generating random numbers. Be aware that Math.random() may not be cryptographically secure, but it is sufficient for this problem.

Notes

The Fisher-Yates shuffle algorithm works by iterating through the array from the last element to the first. In each iteration, it swaps the current element with a randomly chosen element from the portion of the array that has not yet been shuffled. This ensures that each element has an equal probability of ending up in any position in the shuffled array. Consider how to efficiently generate a random index within the unsorted portion of the array.