Shuffling an array only returns part of the array

Question

I wrote a function that shuffles the elements of an array.

function shuffle(arr) {
  var newarr = [];
  var oldarr = arr;
  for(var i = 0; i < arr.length; i++) {
    var index = Math.floor(Math.random() * arr.length);
    newarr.push(arr[index]);
    arr.splice(index, 1);
  }
  return newarr;
}

For some reason, the function only returns half of the array elements. If an array of 7 elements is passed to it, it returns 4 elements. Similarly, if an array with 8 elements is returned.

Where did I go wrong?

`arr.splice(index, 1);` will reduce the array size each time by 1 — Ashish Ranjan, Jun 07 '18 at 18:33
You modified the length of the array while iterating through it, that's why. — Patrick Roberts, Jun 07 '18 at 18:33
You should consider implementing a [Fisher Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle), which is capable of an efficient, in-place shuffle with an even distribution of possibilities for all permutations, assuming the random number generator is also approximately linearly distributed (which it is). — Patrick Roberts, Jun 07 '18 at 18:36
Thanks @HMR, I think it should be `i > 0` rather that `i >= 0`. — Mysterious User, Jun 07 '18 at 18:51
You should learn to use the debugger in your web browser. Place a break point inside your loop and inspect the state of your variables as your loop iterates, and you'll find your problem. — user229044, Jun 07 '18 at 18:54

Matus Dubrava · Accepted Answer · 2018-06-07T18:54:25.077

Just store the length of the array in a variable and use it in a for-loop header instead of arr.length. And that var oldarr = arr line does nothing in your code.

const arr = [1, 2, 3, 4];

function shuffle(arr) {
  var newarr = [];
  const length = arr.length;

  for (var i = 0; i < length; i++) {
    var index = Math.floor(Math.random() * arr.length);
    newarr.push(arr[index]);
    arr.splice(index, 1);
  }

  return newarr;
}

console.log(shuffle(arr));

Note that this is just a quick fix to your problem, not the recommended solution.

And to answer you question - why when you have array of 4 items, the array with only 2 items will be returned - let's look at the execution of that loop where you are decreasing the length of the array in each iteration.

iteration;   i;   arr.length;   i < arr.length
   1         0        4             true
   2         1        3             true
   3         2        2             false

score 1 · Answer 2 · answered Jun 07 '18 at 18:41

There are many Q&A on StackOverflow which provide a correct and efficient algorithm. In your code, the loop variable increments up to arr.length, but in each iteration you diminish that length with splice, so in total, i will only run to about half of the original length, and by consequence your function returns an array of about half the input size.

Quick fix: instead of the for loop, use a while loop:

while (arr.length) {

Optional: in order to leave the input array in tact, replace the following useless assignment:

var oldarr = arr;

...with a copy statement:

arr = arr.slice();

Shuffling an array only returns part of the array

2 Answers2