What are the disadvantages of my shuffle function?

Question

After reading through some "how to shuffle" questions on SO, I saw that this answer was generally accepted:

function shuffle (array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

But what would the problems be with just picking the elements in the list randomly, like I posted:

function shuffle (array) {
  var result = [];
  while(array.length){
    var index = Math.floor(Math.random() * array.length);
    result.push(array.splice(index, 1)[0]);
  }  
  return result;
}

@Durga That doesn't matter though. It's splicing the value so it's not going to be selected after it is — Andrew Li, Jul 30 '17 at 16:00
This is a really great explanation, which includes your method: https://bost.ocks.org/mike/shuffle/ — Mark, Jul 30 '17 at 16:07

Dij · Accepted Answer · 2017-07-30T16:10:37.373

2

There doesn't seem to be anything wrong with the result given by your answer, it does seem to shuffle the array as you pick up a random index and then push it to the resulting array.

The difference between the two approaches is of efficiency, the first solution has a worst case time complexity of O(n) and your solution has a worst case time complexity of O(n^2) as splice has a worst case complexity of O(n) and there is a while loop taking O(n), also the second approach has a space complexity of O(n).

edited Jul 30 '17 at 16:10

answered Jul 30 '17 at 16:02

Dij

9,761
4
18
35

Thankyou. You're answer made me realize that the two shuffle functions in the questions are remarkably similar. – Thomas Wagenaar Jul 31 '17 at 12:59

guest271314 · Answer 2 · 2017-07-30T16:08:00.350

0

You could call .slice() on original array before while loop to preserve the original array.

function shuffle (array) {
  var result = [];
  var temp = array.slice(0);
  while(temp.length){
    var index = Math.floor(Math.random() * temp.length);
    result.push(temp.splice(index, 1)[0]);
  }  
  return result;
}

edited Jul 30 '17 at 16:08

answered Jul 30 '17 at 15:59

guest271314

1
15
104
177

1

A disadvantage is efficiency. I'm not sure splicing is the best operation here; it's definitively not as efficient as the former I would think. – Andrew Li Jul 30 '17 at 16:02
@AndrewLi We can avoid speculation by creating benchmarks for each approach – guest271314 Jul 30 '17 at 16:03
Well the time complexity of each approach speaks for itself. Splicing is O(n), so iterating and splicing would be O(n * n). Just a while loop and array access would be O(n * 1). – Andrew Li Jul 30 '17 at 16:04
@AndrewLi Am still not versed in time complexity verbage. That is one area where this user needs to invest more time in fully gathering the principles. Will remove the first sentence from Answer. – guest271314 Jul 30 '17 at 16:06
@AndrewLi Curious what the time complexity is of an approach using `.forEach()` and `setTimeout()` https://jsfiddle.net/jyqo9ego/? – guest271314 Jul 30 '17 at 16:16
Still O(n). The function will only ever iterate N times, where N is directly proportional for any input X which is the array length. – Andrew Li Jul 30 '17 at 17:14
@AndrewLi Found https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm. Am still reading the answers trying to grasp the concept. – guest271314 Jul 30 '17 at 17:16

score 0 · Answer 3 · answered Jul 30 '17 at 16:05

The obvious problem is that while your solution constructs a new result array, it also empties the argument array which is an absolute bad practise. Don't mutate your arguments unnecessarily. Also, using splice is pretty inefficient as it moves around all elements after the removed one.

What are the disadvantages of my shuffle function?

3 Answers3

Linked