58
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

# Array#sort実装のshuffleは偏る

## シャッフル実装

Fisher-Yatesアルゴリズムで実装された`goodShuffle`と巷で見つけたsort実装の`badShuffle`を5個用意。

``````var goodShuffle = function (arr) {
var i, j, temp;
arr = arr.slice();
i = arr.length;
if (i === 0) {
return arr;
}
while (--i) {
j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};

var badShuffle1 = function (arr) {
return arr.slice().sort(function () {
return Math.round(Math.random() * 2) - 1;
});
};

var badShuffle2 = function (arr) {
return arr.slice().sort(function () {
return Math.round(Math.random());
});
};

var badShuffle3 = function (arr) {
return arr.slice().sort(function () {
return Math.random() - Math.random();
});
};

var badShuffle4 = function (arr) {
return arr.slice().sort(function () {
return parseInt(Math.random() * 3, 10) - 1;
});
};

var badShuffle5 = function (arr) {
return arr.slice().sort(function () {
if (Math.random() > 0.5) {
return 1;
} else {
return -1;
}
});
};
``````

## 均等に分布しているかを調べるメソッドを実装

``````var array = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'];
var times = 1000;
var trial = function (shuffle) {
var arr, average, elem, i, j, len;
average = {};
for (i = 0, len = array.length; i < len; i++) {
average[array[i]] = 0;
}
i = times;
while (i--) {
arr = shuffle(array);
for (j = 0, len = arr.length; j < len; j++) {
elem = arr[j];
average[elem] += j;
}
}
for (elem in average) {
average[elem] /= times;
}
return average;
};
``````

## 結果

### Fisher-Yatesアルゴリズム

4.5近辺なので均等に混ざっているといえる。

``````console.log(trial(goodShuffle));
{ A: 4.579,
B: 4.358,
C: 4.487,
D: 4.575,
E: 4.541,
F: 4.341,
G: 4.522,
H: 4.519,
I: 4.646,
J: 4.432 }
``````

### Array#sort実装

``````console.log(trial(badShuffle1));
{ A: 0.38,
B: 1.16,
C: 2.023,
D: 2.985,
E: 3.949,
F: 5.01,
G: 6.013,
H: 6.915,
I: 7.896,
J: 8.669 }
``````
``````console.log(trial(badShuffle2));
{ A: 1.539,
B: 1.55,
C: 2.288,
D: 3.108,
E: 4.079,
F: 4.876,
G: 5.665,
H: 6.565,
I: 7.314,
J: 8.016 }
``````
``````console.log(trial(badShuffle3));
{ A: 1.65,
B: 1.674,
C: 2.255,
D: 3.123,
E: 4.014,
F: 4.788,
G: 5.748,
H: 6.471,
I: 7.327,
J: 7.95 }
``````
``````console.log(trial(badShuffle4));
{ A: 0.724,
B: 1.155,
C: 2.119,
D: 2.929,
E: 3.967,
F: 4.991,
G: 5.949,
H: 6.956,
I: 7.707,
J: 8.503 }
``````
``````console.log(trial(badShuffle5));
{ A: 1.624,
B: 1.653,
C: 2.117,
D: 3.068,
E: 3.899,
F: 4.94,
G: 5.779,
H: 6.625,
I: 7.296,
J: 7.999 }
``````

## 結論

Fisher-Yatesアルゴリズムを使おう。

## 関連

Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away