· 개발

sort(() => Math.random() - 0.5)로 섞으면 안 되는 이유: Fisher–Yates 셔플

랜덤 비교 함수로 배열을 섞으면 왜 고르게 섞이지 않는지 ECMAScript 명세로 확인하고, 모든 순열이 같은 확률로 나오는 Fisher–Yates 셔플과 난수 범위·생성기 주의점을 정리했습니다.

개발알고리즘

배열을 무작위로 섞는 코드를 찾아보면 이런 한 줄이 자주 나옵니다.

const shuffled = items.sort(() => Math.random() - 0.5);

짧고 그럴듯하지만 결과는 고르게 섞이지 않습니다. ['A', 'B', 'C']를 이 방식으로 60만 번 섞어 순서별 비율을 세어 봤습니다.

순서 비율
ABC 37.4%
ACB 6.2%
BAC 12.5%
BCA 6.3%
CAB 6.3%
CBA 31.3%

고르게 섞인다면 여섯 순서가 모두 약 16.7%여야 합니다. 위 수치는 Node.js v24.13.0에서 관찰한 결과이고, 다른 엔진이나 버전에서는 분포가 달라질 수 있습니다. 엔진마다 달라질 수 있다는 점부터가 문제입니다.

명세는 이 사용법을 보장하지 않는다

ECMAScript 명세는 sort의 정렬 순서 보장을 비교 함수가 “일관된 비교자(consistent comparator)“라는 전제 위에서 정의합니다. 일관된 비교자의 첫 번째 조건은 같은 두 값 a, b로 호출하면 항상 같은 값을 돌려줘야 한다는 것입니다. Math.random() - 0.5는 같은 쌍으로 다시 호출했을 때 다른 값, 때로는 다른 부호를 돌려줄 수 있으므로 이 조건을 어깁니다. 그러면 명세는 정렬 결과의 순서를 구현이 정한다(implementation-defined)고만 적고 있습니다. 결과의 분포는 엔진의 정렬 알고리즘이 어떤 쌍을 몇 번 비교하느냐에 달려 있고, 고른 분포는 어디에서도 약속되지 않습니다.

아무 자리와 바꾸는 방법도 치우친다

정렬 없이 직접 섞는 코드에도 흔한 실수가 있습니다. 각 위치 i에서 전체 범위의 아무 자리 j와 바꾸는 방식입니다.

// 치우친 방식
for (let i = 0; i < a.length; i++) {
  const j = Math.floor(Math.random() * a.length);
  [a[i], a[j]] = [a[j], a[i]];
}

원소가 3개면 선택의 경우의 수는 3 × 3 × 3 = 27이고, 가능한 순열은 6개입니다. 27은 6으로 나누어떨어지지 않으므로 모든 순열이 같은 횟수로 나올 수 없습니다. 27가지를 모두 따라가 보면 ABC·CAB·CBA는 4번, ACB·BAC·BCA는 5번 나옵니다. 일반적으로 n이 3 이상이면 n과 n−1은 서로소라 n^n이 n−1로, 따라서 n!로도 나누어떨어지지 않습니다. 이 방식은 원소가 셋 이상이면 항상 치우칩니다.

Fisher–Yates: 아직 확정되지 않은 칸에서만 고른다

고르게 섞으려면 뒤에서부터 한 칸씩 확정해 나갑니다. 위치 i에서는 0부터 i까지, 즉 아직 확정되지 않은 칸 중 하나를 골라 바꿉니다.

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

선택의 경우의 수는 n × (n−1) × … × 2 = n!이고, 각 순열은 정확히 한 가지 선택 경로로만 만들어집니다. 그래서 j가 범위 안에서 고르게 뽑힌다면 모든 순열의 확률이 1/n!로 같습니다. 반복은 n−1번이므로 시간은 O(n)입니다.

표준 라이브러리에서도 같은 구조를 볼 수 있습니다. Java Collections.shuffle 문서는 리스트를 마지막 원소부터 두 번째 원소까지 거꾸로 돌며, 첫 원소부터 현재 위치까지에서 고른 원소를 현재 위치로 바꿔 넣는다고 설명합니다. CPython의 random.shuffle과 Go math/rand/v2의 Shuffle도 소스 코드를 보면 같은 반복문이고, Go 소스 주석에는 Fisher–Yates라는 이름이 적혀 있습니다.

알고리즘이 맞아도 난수가 문제일 수 있다

Fisher–Yates가 고른 결과를 내는 것은 j가 고르게 뽑힌다는 전제 위에서입니다.

  • 범위. Math.floor(Math.random() * (i + 1))은 0 이상 i+1 미만의 정수를 줍니다. MDN의 getRandomInt 예제와 같은 범위입니다. i + 1 대신 i를 쓰면 j가 i가 될 수 없습니다. 그러면 마지막 칸에는 처음부터 다른 원소가 들어가서, 원래 순서 그대로인 결과 같은 일부 순열이 아예 나오지 않습니다.
  • 나머지 연산 치우침. 32비트 정수 난수를 % n으로 줄이면 2^32가 n으로 나누어떨어지지 않을 때 작은 값이 조금 더 자주 나옵니다. 2^32를 6으로 나눈 나머지는 4이므로 03이 45보다 한 번씩 더 대응됩니다. 이를 피하려면 % n을 하기 전에 floor(2^32 / n) × n 이상인 값을 버리고 다시 뽑습니다. 남은 값의 개수가 n의 배수가 되어 0부터 n−1까지가 같은 횟수로 대응됩니다. CPython의 _randbelow도 다시 뽑기를 쓰는데, 필요한 비트 수만큼 뽑은 값이 n 이상이면 다시 뽑는 방식입니다.
  • 보안. MDN은 Math.random()이 암호학적으로 안전한 난수를 주지 않으니 보안과 관련된 곳에는 crypto.getRandomValues()를 쓰라고 안내합니다. Python 문서도 보안 용도에는 random 대신 secrets 모듈을 권합니다. 결과를 예측당하면 곤란한 추첨이라면 생성기부터 바꿔야 합니다.
  • 생성기의 주기. Python 문서는 길이가 조금만 길어져도 순열의 수가 대부분의 난수 생성기 주기보다 커져서, 긴 시퀀스의 순열 대부분은 만들어질 수 없다고 적고 있습니다. 메르센 트위스터(주기 2^19937−1)의 주기 안에 모든 순열이 들어가는 최대 길이는 2080입니다. Java 문서가 “approximately equal likelihood”라고 쓰는 이유도 바로 이것입니다. 문서는 기본 난수원이 편향 없는 독립 비트원에 근사할 뿐이기 때문이라고 밝힙니다.

몇 개만 뽑을 때

n개 중 k개만 필요하면(0 ≤ k < n) 반복을 k번만 돌려도 됩니다. 뒤에서부터 섞었다면 마지막 k칸이 무작위 표본입니다. k가 n이면 위 함수처럼 n−1번 돌리면 됩니다. Python이라면 random.sample(population, k)가 원본을 건드리지 않고 비복원 추출로 k개를 뽑아 뽑힌 순서대로 돌려줍니다. 원본에 같은 값이 여러 개 있으면 결과에도 같은 값이 여러 번 나올 수 있습니다.

이 사이트의 제비뽑기 · 팀 나누기 도구도 Fisher–Yates로 섞습니다. j는 crypto.getRandomValues()로 얻은 32비트 값 가운데 floor(2^32 / n) × n 이상인 값을 버리고 다시 뽑는 방식으로 고릅니다.

블로그로