JavaScript 實作 Array Shuffle

前一段時間，在工作時剛好需要用到 Array shuffle 的功能。
隨手 google 看到個一行又簡潔的array shuffle，是透過 Array.sort 將
Math.random() - 0.5 作為 compare function 傳入：

array.sort(() => Math.random() - 0.5)

這段 Compare function 邏輯怎麼讀？

1. 首先， Math.random() 會回傳一個介於 0 ~ 1 的浮點數數字。
2. 接著， Math.random() - 0.5 就代表會得到一個介於 -0.5 ~ 0.5 的浮點數數字。

如此一來，Math.random() - 0.5 的結果就是負數、正數、零，三種可能。

再搭配 MDN 上對 sort 函式對 compare function 回傳值的行為定義：

Array.prototype.sort() MDN

• 若 compareFunction(a, b) 的回傳值小於 0，則會把 a 排在小於 b 之索引的位置，即 a 排在 b 前面。
• 若 compareFunction(a, b) 回傳 0，則 a 與 b 皆不會改變彼此的順序，但會與其他全部的元素比較來排序。備註：ECMAscript 標準並不保證這個行為，因此不是所有瀏覽器（如 Mozilla 版本在 2003 以前）都遵守此行為。
• 若 compareFunction(a, b) 的回傳值大於 0，則會把 b 排在小於 a 之索引的位置，即 b 排在 a 前面。

這樣，就輕鬆達到陣列 shuffle 的目的了

實際運作結果

看起來挺簡單的，但是實際上運作結果是如何呢？

來寫個程式試試看吧

環境： Node.js v14.15.0.

// shuffle function
function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

// 結果計數器
const resultCounter = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '312': 0,
  '321': 0,
}

// 執行一百萬次測試
for (let i = 0; i < 100 * 10000; i += 1) {
  let array = [1, 2, 3];
  shuffle(array);

  const result = array.join('');
  resultCounter[result] += 1;
}

// 把計數計全部 log 出來看看結果
for (let result in resultCounter) {
  console.log(`${result}: ${resultCounter[result]}`);
}

執行結果如下

123: 374999
132: 62652
213: 124916
231: 62507
312: 62305
321: 312621

我們可以看到，其實這樣的運作結果，並不是隨機分佈唷

Fisher-Yates Shuffle

Fisher-Yates Shuffle 是個簡單的亂數排序演算法，適合用在有限的序列中做隨機亂數排序

我們來用 Fisher-Yates 的 JavaScript 程式試試看結果：

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

實際來測試看看結果，這次得到的結果是

123: 166857
132: 166403
213: 166606
231: 167090
312: 167162
321: 165882

相較於上面採用 Math.random() - 0.5 的方式，可以看到執行結果分佈平均許多

同時 Fisher-Yates 演算法的時間複雜度為: O(n)

有類似需求的朋友，不訪使用看看吧