개념과 배경

배열을 무작위로 섞을 때 Array.prototype.sort와 Math.random을 조합한 패턴이 흔히 보임

array.sort(() => Math.random() - 0.5) 형태는 간단해 보이지만 결과 분포가 한쪽으로 치우치는 편향이 발생함

간단한 실험으로 [1, 2, 3]을 백만 회 섞어 빈도를 집계해 보면 특정 순열이 과도하게 많이 나오거나 적게 나오는 경향 관찰됨

핵심은 Math.random 자체보다 sort에 전달된 비교 함수가 랜덤하게 일관성 없이 값을 내놓는 구조라는 점임

왜 sort + random이 편향되는가

정렬 알고리즘은 비교 함수가 다음 성질을 만족한다고 가정함

  • 반대칭과 추이성 보장
  • 같은 두 원소 비교 시 항상 같은 결과 반환

하지만 () => Math.random() - 0.5는 같은 두 원소 쌍이라도 호출할 때마다 결과가 달라짐

  • 비교 결과의 비일관성으로 인해 정렬 알고리즘 동작이 정의에 가까운 보장 범위를 벗어남
  • 엔진별 정렬 구현과 안정성 여부, 피벗 선택 전략 등에 따라 특정 패턴이 더 자주 발생하는 편향이 생김

즉 문제의 주된 원인은 비교 함수의 무작위성으로 인한 추이성 붕괴와 구현 의존성임

참고로 Math.random은 자바스크립트 표준상 균등 분포의 유사난수를 제공하는 것이 목적이며 암호학적 보안은 보장하지 않음 보안 목적에는 window.crypto.getRandomValues 사용 권장

올바른 해결책 피셔‑예이츠 셔플

피셔‑예이츠 셔플은 모든 순열을 동일 확률로 생성하는 균등 셔플 알고리즘임 배열의 끝에서 시작해 i 인덱스를 0 이상 i 이하에서 균일하게 고른 j와 교환하는 과정을 반복함

  • i를 n-1에서 1까지 감소시키며 한 번씩 정확히 교환 수행
  • 각 단계에서 선택 범위를 점차 줄이므로 중복 선택 없이 균등한 순열 공간을 탐색

간단 구현 예시

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

위 구현은 i 단계에서 j를 0 이상 i 이하로 균일 추출해야 함 Math.floor(Math.random() * (i + 1)) 형태가 이 조건을 충족함

검증 관찰

동일한 실험으로 [1, 2, 3]을 백만 회 셔플해 순열 빈도를 집계하면 모든 순열의 발생 비율이 거의 동일하게 수렴하는 패턴 관찰됨 샘플링 오차 범위 내에서 균등 분포 근사 확인 가능

주의사항과 베스트 프랙티스

  • sort에 랜덤 비교 함수를 넘겨 셔플 구현하지 말 것
  • 피셔‑예이츠에서 j 범위는 0 이상 i 이하가 되어야 하며 오프바이원 주의
  • Math.random은 보안용 아님, 게임 보상이나 추첨 등 금전적 가치가 걸린 시나리오에서는 암호학적 난원 필요
  • 보안 민감 시 Web Crypto 기반으로 무작위 정수를 만들고 같은 알고리즘에 주입

암호학적 난수로 정수를 얻는 최소 스니펫 예시

function cryptoRandomInt(maxExclusive) {
  const buf = new Uint32Array(1)
  window.crypto.getRandomValues(buf)
  return buf[0] % maxExclusive
}

실무에서는 모듈러 편향을 피하려면 거부 샘플링 등 추가 처리가 필요할 수 있음

정리

sort + Math.random 패턴은 비교 함수의 비일관성 때문에 구현 의존적 편향 발생 가능성이 큼 균등한 셔플이 필요하면 피셔‑예이츠 셔플 사용 보안 요구가 있으면 난수 소스를 Web Crypto로 교체하고 동일 알고리즘을 적용 이 조합이 단순하며 빠르고 분포 품질도 신뢰 가능

참고자료