Javascript - 배열의 요소를 무작위로 섞는 방법 [array, shuffle]

자바스크립트는 자바의 Connections.shuffle()와 같은 배열의 요소를 랜덤 한 방법으로 바꾸는 기능을 제공하지 않습니다. 그렇기 때문에 자바스크립트에서는 배열의 요소를 무작위로 섞기 위해서는 기능을 구현해서 사용해야 합니다.

자바스크립트로 배열의 요소를 무작위로 섞기

 자바스크립트에서 배열 요소를 무작위로 섞기 위해서는 Array.sort()와 Math.random()를 사용하면 됩니다. 그럼 예제를 통해서 정확히 어떻게 사용하는지 알아보겠습니다.

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

const numbers = [1, 2, 3];
shuffle(numbers);

 shuffle라는 이름을 가진 함수는 배열(array)을 인자로 받아서, Array.sort() 기능을 이용해 배열의 요소 순서를 변경합니다. 배열의 요소 순서는 0 이상 1 미만의 부동소수점 난수 값을 반환하는 Math.random()를 사용합니다. Math.random()을 통해 반환받은 값에서 0.5를 빼면 무작위로 0보다 작은 수를 반환하기 때문에 Array.sort()에 식으로 사용하면 배열의 요소 순서가 무작위로 변경됩니다.

 

 즉 양수와 음수를 무작위로 반환하는 판별식을 이용해서 배열의 정렬 기능에 대입해 배열의 요소를 무작위로 바꾸는 방법입니다. 그럼 위의 예제 코드를 사용하면 어떤 결과가 나오는지 확인해보겠습니다.

배열의 요소를 Array.sort()와 Math.random()를 사용해서 무작위로 섞은 결과

 예상대로 numbers 배열의 숫자들이 무작위로 변경된 내용을 확인할 수 있습니다. 그럼 Math.random()이 편향적이지 않고 랜덤 하게 결과를 반환하는지 확인해볼까요?

  for (let count = 1; count <= 100000; count++) {
    shuffle(numbers);
    setResult(numbers.join(''));
  }

 10만 번 정도 shuffle() 함수를 통해 배열을 섞고 결과를 확인하면 아래와 같은 결과를 확인할 수 있습니다. 브라우저 혹은 브라우저 엔진마다 결과는 달라지겠지만, Math.random()은 우려와 달리 무작위 값을 반환하는 것을 알 수 있습니다.

10만번의 shuffle 수행 결과

 그런데 여기서 고민할 부분이 한 가지 있습니다. 지금 실행한 환경에서는 Math.random()이 편향적이지 않은 결과를 반환했지만, 모든 환경에서 무작위로 값을 잘 반환하는지 알 수 없다는 문제가 남아있습니다. 그럼 어떻게 하면 좋을까요?

 

 

피셔-예이츠 셔플(Fisher-Yates shuffle)을 활용한 배열 섞기

 어떤 상황에서든 의도하는 결과가 나오게 하는 방법은 바로 무작위 판별식을 직접 정의하고 사용하는 방법입니다. 이게 정답이다.라는 말을 쓸 수는 없지만 무작위로 값을 섞을 때 사용하는 알고리즘 중에 가장 대표적인 알고리즘이 바로 피셔-예이츠 셔플(Fisher-Yates shuffle)입니다. 오늘은 이 알고리즘을 사용해서 Array.sort()와 Math.random()을 사용하지 않고 배열을 무작위로 섞는 방법을 알아보겠습니다.

 

 피셔-예이츠 셔플은 배열이 가진 요소를 무작위로 하나씩 지워가면서 새로운 순서를 정의하는 방법입니다. 글보다는 이미지로 보는 게 이해가 쉬워 위키에 있는 사진을 가져왔습니다.

https://en.wikipedia.org/wiki/Fisher-Yates_shuffle - 위키 내용 일부 발췌

 연필과 종이 방법인데 종이에 섞어야 할 값을 나열하고, 임의 값을 선점해 값을 하나씩 지우면서 새로운 순서를 정의하는 방법입니다. 위의 내용을 코드로 만들면 아래와 같은 코드로 만들 수 있습니다.

function shuffle(array) {
  for (let index = array.length - 1; index > 0; index--) {
    // 무작위 index 값을 만든다. (0 이상의 배열 길이 값)
    const randomPosition = Math.floor(Math.random() * (index + 1));

    // 임시로 원본 값을 저장하고, randomPosition을 사용해 배열 요소를 섞는다.
    const temporary = array[index];
    array[index] = array[randomPosition];
    array[randomPosition] = temporary;
  }
}

 처음에 만든 예제 코드와 달리 Array.sort()를 사용하지 않고 배열을 무작위로 섞을 수 있는 코드가 만들어졌습니다. 여전히 Math.random()은 사용하고 있지만 여기서 사용하는 Math.random()은 키가 되지 않기 때문에 문제가 되지 않습니다. 

피셔-예이츠 셔플(Fisher-Yates shuffle) 적용 결과

 피셔-예이츠 셔플 알고리즘을 통해 만든 코드를 처음에 만든 코드에 적용시켜 결과를 확인해보면 이와 같은 결과를 확인 할 수 있습니다. 처음에 만든 예제 코드와 결과가 크게 다르지 않습니다. 무작위 결과가 한쪽으로 치우지지 않고 정상적으로 동작했음을 알 수 있습니다.

 

 위에서 사용한 예제 코드들은 하나의 파일로 만들어 첨부하였습니다. 실제 코드 내용 결과를 테스트하거나 확인하고 싶으신분은 첨부 파일을 다운로드 받아서 사용해보세요.

배열 요소를 무작위로 섞는 방법.zip

0.00MB