JavaScript: Shuffling Array Elements

Shuffle is different than random in term. But indeed randomness is applied in shuffling.

As in shuffling cards and giving out one random card, those are different.

Algorithmically, we can loop through the reference array, generate random index based on the reference array length, then put that item (with that random index) to a new array.

But since random can generate similar number (being floored or rounded down) as previous one, that can lead to duplicates.

For example

We have an array:

["a", "b", "c", "d"]

Then loop through it while blindly creating a random index to copy the randomly chosen item to a new array, surely there will be duplicates.

Unwanted output:

["c", "a", "a", "d"] ["d", "b", "b", "b"] ["a", "a", "c", "a"]

---

Deletion

We need to trim the array reference after one element gets picked by the random index.

Example array input:

["a", "b", "c", "d"]

Then we want to shuffle the array input.

• Create a clone of the original array (clonedArray), so that nothing will happen to the original one.

  Then create an empty array (bufferArray) to store the shuffled elements.

• Loop through the clonedArray to randomly pick an element from it, then place that chosen element to bufferArray. Then delete/remove that particular element from the clonedArray.

  For instance this is the initial clonedArray:

  ["a", "b", "c", "d"]

  First loop, it generates random index of 1.

  That means the element "b" (index 1) is picked from the clonedArray.

  Then we put that picked element to the bufferArray then delete that element from clonedArray.

  bufferArray = ["b"] clonedArray = ["a", "c", "d"]

  And after that, the loop continues, we get another random index as 1, no problem, because the clonedArray is different now.

  So, the next picked element (with index 1) from ["a", "c", "d"] is "c".

  Now we have:

  bufferArray = ["b", "c"] clonedArray = ["a", "d"]

  And so on.

  As you can see in that looping sequence, the clonedArray length will decrease until it's empty, and the bufferArray length will increase and it will have the shuffled items.

---

Code

This is my original code back in 2015 (first published) with minor adjustment of camel casing the variable names and default function parameter (arr = []).

function shuffle(arr = []) { var clonedArray = arr.slice(); var newArray = []; var index; for (var i = 0; i < arr.length; i++) { // Generate random index based on clonedArray length. index = Math.floor(Math.random() * clonedArray.length); // Push the randomly picked element to newArray. newArray.push(clonedArray[index]); // Remove the picked element from clonedArray // clonedArray length will be decreased by 1. clonedArray.splice(index, 1); } return newArray; }

The original array, with the variable arr, will be left intact.

That shuffle function above can be cascaded, like so:

shuffle(shuffle(shuffle(shuffle(arrayInput))));

To shuffle the original array four times.

---

Using do-while, while, and forEach

// Using [do-while] function shuffle(arr = []) { var clonedArray = arr.slice(); var newArray = []; var i = 0; var index; do { index = Math.floor(Math.random() * clonedArray.length); newArray.push(clonedArray[index]); clonedArray.splice(index, 1); i++; } while (i < arr.length); return newArray; } // Using [while] function shuffle(arr = []) { var clonedArray = arr.slice(); var newArray = []; var i = 0; var index; while (i < arr.length) { index = Math.floor(Math.random() * clonedArray.length); newArray.push(clonedArray[index]); clonedArray.splice(index, 1); i++; } return newArray; } // Using [forEach] function shuffle(arr = []) { var clonedArray = arr.slice(); var newArray = []; var index; arr.forEach(function () { index = Math.floor(Math.random() * clonedArray.length); newArray.push(clonedArray[index]); clonedArray.splice(index, 1); }); return newArray; }

Each of those will behave similarly as the first code snippet.

---

Fisher-Yates BOSS Technique

This technique is the most efficient, introduced by Richard Durstenfeld in 1964. This is the description at Wikipedia.

Let's take the snippet from Wikipedia:

function shuffleArray(array) { for (let i = array.length - 1; i >= 1; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]]; } }

The technique is straightforward, without introducing mutation to the clonedArray or any other computation. Get random index, then swap, BAM!

But as you can see above, the snippet doesn't return anything. It's just snippet of the technique.

This is the proper vibe.

function fisherYatesShuffle(arr = []) { if (!arr.length) return []; const shuffled = arr.slice(); for (let i = shuffled.length - 1; i >= 1; i--) { const j = Math.floor(Math.random() * (i + 1)); [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]; } return shuffled; }

That is actually EFFICIENT! 😲 🥳

It generates similar to the prior concept, but with peak efficiency.

The problem with pure randomness, the shuffled array can have similar sequence.

At some point, this input:

["a", "b", "c", "d"]

Can be shuffled as:

["a", "b", "c", "d"]

We want to ensure the generated sequence always differs from the original input.

We can add if condition within the loop, and we need while to accomplish it, as such:

function shuffleItReal(arr = []) { if (!arr.length) return []; const newArray = arr.slice(); let i = newArray.length; while (i > 1) { const j = Math.floor(Math.random() * i); // Gates the Fisher-Yates BOSS pure random logic. if (arr.length > 1 && j === arr.length - 1) continue; i -= 1; [newArray[i], newArray[j]] = [newArray[j], newArray[i]]; } return newArray; }

I implement while so that there is no extra overhead inside the loop. I am only interested in simple boolean check within the loop.

The function shuffleItReal above will act as efficient as fisherYatesShuffle, but with addition that it will always generate different sequence than the reference array.

---

Benchmark

Let's make a default array with 10,000 items, invoke each technique 1,000 times, and measure the completion duration of it.

function shuffleItReal(arr = []) { if (!arr.length) return []; const newArray = arr.slice(); let i = newArray.length; while (i > 1) { const j = Math.floor(Math.random() * i); if (arr.length > 1 && j === arr.length - 1) continue; i -= 1; [newArray[i], newArray[j]] = [newArray[j], newArray[i]]; } return newArray; } function fisherYatesShuffle(arr = []) { if (!arr.length) return []; const shuffled = arr.slice(); for (let i = shuffled.length - 1; i >= 1; i--) { const j = Math.floor(Math.random() * (i + 1)); [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]; } return shuffled; } function shuffle(arr = []) { var clonedArray = arr.slice(); var newArray = []; var index; for (var i = 0; i < clonedArray.length; i++) { index = Math.floor(Math.random() * clonedArray.length); newArray.push(clonedArray[index]); clonedArray.splice(index, 1); } return newArray; } function benchmarkShuffleMethods(size = 10000, iterations = 1000) { const array = Array.from({ length: size }, (_, i) => i); let start = performance.now(); for (let i = 0; i < iterations; i++) shuffleItReal(array); let shuffle2025Time = performance.now() - start; start = performance.now(); for (let i = 0; i < iterations; i++) fisherYatesShuffle(array); let fisherYatesTime = performance.now() - start; start = performance.now(); for (let i = 0; i < iterations; i++) shuffle(array); let shuffle2015Time = performance.now() - start; console.log(`Shuffle 2015 (Deletion technique: pure random shuffle): ${shuffle2015Time.toFixed(3)} ms`); console.log(`Fisher-Yates (BOSS technique: pure random shuffle): ${fisherYatesTime.toFixed(3)} ms`); console.log(`Shuffle 2025 (BOSS technique + avoid similar sequence): ${shuffle2025Time.toFixed(3)} ms`); return `DONE ${new Date().toISOString()}`; } benchmarkShuffleMethods();

This is the snapshot of the results:

And this is the BOSS technique + same sequence avoidance.

/** * Shuffles the elements of an array, ensuring a different order. * * @param {any[]} - The input array to shuffle. * @returns {any[]} A new array with the shuffled items. */ function shuffleItReal(arr = []) { if (!arr.length) return []; const newArray = arr.slice(); let i = newArray.length; while (i > 1) { const j = Math.floor(Math.random() * i); // Gates the Fisher-Yates BOSS pure random logic. if (arr.length > 1 && j === arr.length - 1) continue; i -= 1; [newArray[i], newArray[j]] = [newArray[j], newArray[i]]; } return newArray; }