CODEWITHSUNDEEP
javascript
Thomas Wagenaar
Thomas Wagenaar

Reputation: 6759

What are the disadvantages of my shuffle function?

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;
}

Upvotes: 1

Views: 71

Answers (3)

Dij
Dij

Reputation: 9808

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).

Upvotes: 2

guest271314
guest271314

Reputation: 1

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;
}

Upvotes: 0

Bergi
Bergi

Reputation: 664425

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.

Upvotes: 0

Related Questions