자바스크립트로 배열을 무작위로 섞어야 할 때, 많은 개발자들이 아래와 같은 코드를 떠올립니다.
arr.sort(() => Math.random() - 0.5);간결하고 그럴싸해 보이지만, 이 방법은 통계적으로 편향될 수 있어 실제 프로젝트에서는 절대 사용하면 안 되는 위험한 코드입니다. sort의 비교 함수는 일관성을 기대하는데, 랜덤 값은 그 기대를 완전히 무너뜨리기 때문입니다.
그렇다면 진정으로 공정한 무작위 셔플은 어떻게 구현해야 할까요? 정답은 바로 피셔-예이츠 셔플(Fisher-Yates Shuffle) 알고리즘에 있습니다.
피셔-예이츠 셔플이란?
피셔-예이츠 셔플은 편향되지 않은 무작위 순열을 만들기 위한 가장 대표적인 알고리즘입니다.
핵심 원리:
배열의 각 요소를 순회하며, 현재 위치의 요소를 '아직 섞이지 않은' 부분에 있는 무작위 요소와 자리를 바꾼다.
이 과정을 통해 모든 요소가 모든 위치에 올 확률이 동일해져, 통계적으로 완벽한 무작위성을 보장할 수 있습니다.
알고리즘 동작 원리 (In-place 방식)
현대적인 피셔-예이츠 알고리즘은 배열을 뒤에서부터 순회하며 '섞기 완료된 안전지대'를 만들어가는 방식을 사용합니다.
let arr = [1, 2, 3] 예제로 따라가 보겠습니다.-
마지막 자리(
i = 2)를 결정합니다.- 섞을 범위:
[1, 2, 3](인덱스 0 ~ 2) - 이 범위에서 무작위 인덱스
j를 뽑습니다. (예:j = 0) arr[2]와arr[0]의 자리를 바꿉니다. →[3, 2, 1]- 이제 맨 뒤의
1은 자리가 확정된 '안전지대'입니다.
- 섞을 범위:
-
두 번째 자리(
i = 1)를 결정합니다.- 섞을 범위:
[3, 2](인덱스 0 ~ 1) 안전지대는 제외 - 이 범위에서 무작위 인덱스
j를 뽑습니다. (예:j = 1) arr[1]과arr[1]의 자리를 바꿉니다. →[3, 2, 1]- 이제
2의 자리도 확정되어 안전지대는[2, 1]로 넓어집니다.
- 섞을 범위:
이 과정을 i가 0보다 클 때까지만 반복하면, 배열 전체가 공정하게 섞입니다. 앞에서부터 순회하는 것도 가능하지만, 뒤에서부터 진행하는 것이 더 고전적이고 일반적인 구현 방식입니다.
JavaScript 구현 및 코드 해설
function shuffle(arr) {
// 배열의 맨 마지막 요소부터 시작해서 두 번째 요소까지 역순으로 순회
for (let i = arr.length - 1; i > 0; i--) {
// 0부터 i까지의 인덱스 중에서 무작위 인덱스를 하나 선택
let j = Math.floor(Math.random() * (i + 1));
// 현재 요소(i)와 무작위로 선택된 요소(j)의 자리를 바꿈
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}Math.floor(Math.random() * (i + 1)) 분석
i + 1: 섞어야 할 범위의 크기를 구합니다. (예:i가 2일 때, 0, 1, 2 세 칸이므로 크기는 3)Math.random() * (i + 1):0이상i + 1미만의 무작위 소수를 생성합니다.Math.floor(...): 소수점을 버려0부터i까지의 무작위 정수 인덱스를 얻습니다.
결론
간결해 보인다는 이유로 sort와 Math.random 조합을 사용하는 것은 통계적으로 편향될 수 있어 버그와 같습니다. 무작위 셔플이 필요할 때는 항상 검증된 피셔-예이츠 알고리즘을 사용하여 예측 가능하고 안정적인 코드를 작성하는 습관을 들입시다!!
감사합니다
