Javascript 배열 요소 랜덤하게 섞기

코딩을 하다보면 배열을 랜덤하게 섞을 상황이 생깁니다.
대부분의 경우, 아래와 같은 코드를 이용해서 배열을 섞고는 하죠.

Array.prototype.sort()를 이용한 방법

function sortShuffle(arr) {
  return arr.sort(() => Math.random() - 0.5);
}

이는 배열을 정렬하는 sort 메서드를 이용해서 새롭게 정렬을 만들어내는 방식인데요, Math.random()의 결과는 0 <= x < 1이므로 0.5를 빼주면 양수이거나 음수가 나와 배열이 섞이는 원리입니다. 저도 이 방식을 즐겨 사용했었습니다. 그러다가 어느 날, 이 방식이 균등한 확률로 섞이게 되는지 궁금해졌습니다.

테스트

그래서 간단하게 테스트를 구성해봤는데요, 해당 함수를 1,000,000번 수행했을 때 얼마나 균일하게 섞이는지를 확인해 보기로 했습니다.

const sortMap = new Map();

for (let i = 0; i < 1000000; i++) {
  const sortAlphabet = ["a", "b", "c"];
  const joinedSortShuffle = sortShuffle(sortAlphabet).join("");

  if (sortMap.has(joinedSortShuffle)) {
    sortMap.set(joinedSortShuffle, sortMap.get(joinedSortShuffle) + 1);
  } else {
    sortMap.set(joinedSortShuffle, 1);
  }
}

결과는 아래와 같았습니다.

별로 균등하게 섞이지 않은 것 같아 보이네요. 🥲

Fisher-Yates Shuffle을 이용한 방법

알고리즘에 대한 자세한 내용은 Wikipedia를 참조하시면 됩니다. 간단히 설명하면 모든 요소들을 뒤에서부터 순회하면서 랜덤한 위치에 있는 요소와 switch하여 섞는 방식입니다. 가장 균일한 결과를 나타내는 알고리즘으로 알고 있는데요, 코드는 아래와 같습니다.

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

테스트

동일한 배열로 동일한 환경에서 테스트를 진행해 보았습니다. 테스트 코드는 아래와 같습니다.

const fisherYatesMap = new Map();

for (let i = 0; i < 1000000; i++) {
  const fisherYatesAlphabet = ["a", "b", "c"];
  const jointedFisherYatesShuffle =
    fisherYatesShuffle(fisherYatesAlphabet).join("");

  if (fisherYatesMap.has(jointedFisherYatesShuffle)) {
    fisherYatesMap.set(
      jointedFisherYatesShuffle,
      fisherYatesMap.get(jointedFisherYatesShuffle) + 1
    );
  } else {
    fisherYatesMap.set(jointedFisherYatesShuffle, 1);
  }
}

결과는 아래와 같습니다.

균등하게 섞인 것 같네요! 😆

주의할 점

한 번만 실행하는 거라면 결과에 크게 상관이 없겠지만, 테스트를 수행할 때는 매 순회때마다 새로운 배열을 할당해야 합니다. 만일 for-loop 바깥 쪽에서 배열을 생성해두고 셔플을 돌리게 되면 직전 결과로 나타난 배열을 다시 셔플하는 결과가 되어, 1,000,000번의 수행 후에는 비슷한 확률로 결과가 수렴하게 되거든요.