피셔-예이츠(Fisher-Yates) 셔플 알고리즘이란?
피셔-예이츠 셔플 알고리즘은 배열의 요소들을 무작위로 섞기 위해 사용되는 알고리즘입니다. 물론 개발자가 직접 셔플 로직을 작성할 수도 있지만, 많은 개발자들이 현대식 피셔-예이츠 셔플 알고리즘을 배열 요소를 섞는 가장 효율적이고 신뢰할 수 있는 방법으로 꼽습니다. 이 알고리즘은 시간 복잡도 O(n)으로 배열을 한 번만 순회하며, 모든 순열이 동일한 확률로 나타나는 편향 없는(unbiased) 셔플을 보장한다는 큰 장점이 있습니다.
알고리즘 동작 단계
- 뒤에서 앞으로 순회: 배열의 마지막 인덱스부터 시작해 앞쪽으로 이동하며 순회합니다. 예를 들어 8개의 요소(A, B, C, D, E, F, G, H)를 가진 배열(인덱스 0~7)이 있다면, 첫 번째 순회는 마지막 인덱스 7의 요소 H에 영향을 줍니다.
- 무작위 인덱스 생성: 선택된 인덱스 7과 인덱스 0 사이에서 무작위 숫자(무작위 인덱스)를 생성합니다. 여기서는 무작위 인덱스가 3이라고 가정해 보겠습니다.
- 요소 교환: 선택된 인덱스의 요소와 무작위 인덱스의 요소를 서로 맞바꿉니다. 무작위 인덱스 3의 요소는 D이므로, 교환 후 배열은 [A, B, C, H, E, F, G, D]가 됩니다.
- 두 번째 순회: 이미 처리가 끝난 마지막 인덱스는 제외하고, 인덱스 0부터 6 사이에서 새로운 무작위 인덱스를 찾습니다. 생성된 무작위 인덱스가 2라고 하면, 인덱스 6의 요소 G와 인덱스 2의 요소 C를 맞바꿉니다. 이제 배열은 [A, B, G, H, E, F, C, D]가 됩니다.
- 반복: 같은 패턴으로 인덱스 6을 제외하고 인덱스 5와 0 사이에서 무작위 인덱스를 찾는 과정을 인덱스 1에 도달할 때까지 반복합니다. 인덱스 0은 그보다 작은 인덱스가 없어 교환 대상이 될 수 없으므로 순회하지 않습니다.
- 예외 상황: 생성된 무작위 인덱스가 현재 순회 중인 인덱스와 같아질 수도 있습니다. 예를 들어 인덱스 4와 0 사이에서 순회 중일 때 무작위 인덱스로 4가 선택되면, 해당 위치의 값은 제자리에 그대로 유지됩니다.
예제 코드
다음 예제는 자바스크립트로 구현한 현대식 피셔-예이츠 셔플 알고리즘입니다.
<html>
<body>
<script>
var arr = ['A','B','C','D','E','F','G','H'];
var i = arr.length, k, temp; // k는 무작위 인덱스 생성용, temp는 값 교환용 변수
while(--i > 0){
k = Math.floor(Math.random() * (i+1));
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
document.write(arr);
</script>
</body>
</html>
실행 결과
C,F,H,D,A,G,E,B // 실행할 때마다 출력 결과는 달라집니다.
이처럼 피셔-예이츠 셔플은 구현이 간단하면서도 공정한 무작위성을 보장하기 때문에 카드 게임 덱 섞기, 퀴즈 문항 순서 랜덤화, 추천 목록 셔플 등 다양한 분야에서 널리 활용되고 있습니다.