[ 자바스크립트(JavaScript) ] shuffle 함수를 만들어보자

📍 shuffle 함수를 만들어보자

JS로 shuffle 함수를 만들 때 가장 먼저 생각나는 메서드는 sort() 일 것이다. 아마도 다음 코드처럼 구성하지 않았을까??

// sort shuffle
const arr = [1, 2, 3, 4, 5];
const shuffle = arr.sort(() => Math.random() - 0.5)

console.log(shuffle);
👉🏾 [ 5, 3, 2, 1, 4 ]

구현 로직을 살펴보면 배열을 순회하면서 Math.random() 메서드를 사용하여 나온 랜덤 한 값에 -0.5를 하여 sort() 메서드를 거치게 된다. 만약, Math.random() - 0.5를 한 값이 양수라면 오름차순으로 정렬되고, 음수를 리턴하면 내림차순으로 정렬된다. arr 배열을 모두 순회하게 되면 상단 코드 블록 6번 Line처럼 배열이 shuffle된 것을 알 수 있다.

 

sort 함수로 구현했을 때의 장점은 코드가 간단해지는 반면, 단점은 모든 확률이 균일하게 일어나지 않는다. (JS 엔진마다 결과가 다를 수 있다.) 그 이유는 sort는 이런 용도로 만들어진 메서드가 아니기 때문이다. 이를 증명하기 위해 다음 코드를 살펴보자. sort 메서드를 이용해 배열 [1, 2, 3]을 백만 번 shuffle 해봤다.

const arr = [1, 2, 3];

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

let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1_000_000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

👉🏾 
123: 375285,
132: 62554,
213: 125270,
231: 62429,
312: 62557,
321: 311905

count를 살펴보면 빈도가 처음, 중간, 끝에 쏠려있는 것을 알 수 있다. 그 이유는 sort 메서드 때문인데, sort를 실행하면 인수로 넘긴 정렬 함수가 배열을 정리해주는데, 이 과정에서 element 비교가 완전 무작위로 이루어지기 때문이다. JS 엔진마다 내부 구현 방식도 달라 이런 혼돈은 더 커지게 된다.

728x90

이를 해결하기 위해 피셔-에이츠(Fisher-Yates) 셔플을 이용하면 편향되지 않은 빈도로 shuffle을 할 수 있고, 시간복잡도도 sort 메소드보다 이점이 있다. Tim sort를 사용한 sort 메소드는 평균 O(nlogn)을 만족하지만, 피셔-에이츠는 O(N)을 만족하기 때문이다. 피셔-에이츠(Fisher-Yates)의 구현순서는 다음과 같다.

 

1. 1부터 N까지의 수 중 임의의 숫자를 선택한다.
2. 1과 선택되지 않고 남아 있는 수 사이의 임의의 수 k를 선택한다.
3. k를 선택되지 않은 마지막 숫자와 자리를 바꾼다.
4. 1부터 N-1까지의 수 중 임의의 숫자를 선택한다.
5. 더 이상 선택할 숫자가 없을 때까지 2~4번의 과정을 반복한다.

 

 

이를 JS코드로 작성하면 다음과 같다.

// Fisher-Yates shuffle
function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {  // 배열의 마지막부터 시작한다. i가 0이되면 반복문을 종료한다.
    let j = Math.floor(Math.random() * (i + 1));  // 랜덤한 값과 현재 인덱스 위치 + 1을 곱하고 소수점을 제거한다.
    [array[i], array[j]] = [array[j], array[i]];  // 현재 인덱스와 랜덤한값에 인덱스 위치 + 1을 곱하고 소수점을 제거한 값과 자리를 바꾼다.
  }
}

타입스크립트로 코드를 가독성 있게 작성해봤다. 그리고 백만 번 shuffle 해봤고 결론적으로 확률이 균일하게 나오는 것을 알 수 있다.

function shuffle<T>(array: T[]) {
  for (let index = array.length - 1; index > 0; index--) {
    const randomIndex = Math.floor(Math.random() * (index + 1))

    [array[index], array[randomIndex]] = [array[randomIndex], array[index]]
  }
  return array
}

let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

👉🏾
123: 166693
132: 166647
213: 166628
231: 167517
312: 166199
321: 166316

이렇게 shuffle 함수를 알아봤는데, 데이터의 크기가 작고 빈도에 상관없이 간편하게 shuffle을 구현하려면 sort를 사용해도 되지만, 데이터의 크기가 크고 발생 빈도가 균일하게 일어나야 한다면 피셔-에이츠의 로직을 사용하는 것이 어떨까?라고 생각하면서 글을 마친다.

 

Reference

1. 피셔-에이츠 셔플
2. Fisher–Yates Shuffle - Mike Bostock
3. How to shuffle an array in JavaScript - YouTube