[Javascript] 배열을 이용한 카드 섞기(Card Shuffle) 구현 알고리즘 기초
카드 섞기는 랜덤 함수로 랜덤 값을 발생시켜서 랜덤 값을 공통적으로 사용합니다.
랜덤 값을 어떻게 사용하는지에 따라 구현 방식이 달라진다고 생각하면 됩니다.
예제로 사용하는 카드의 개수는 12장이고 1~12까지의 숫자를 랜덤 하게 섞는 것을 구현하지만, 배열에 들어있는 배열 요소들이 꼭 숫자가 아니어도 되고, 순서를 가지거나 대소를 비교할 수 있는 값이 아니어도 됩니다.
1. 초 간단 정렬 섞기
정렬 함수를 이용한 초 간단 카드 섞기입니다.
랜덤값이 -0.5 ~ 0.5 사이의 값이 되도록 해서 정렬하는 앞뒤의 요소 순서를 바꿀지 말지를 임의로 정해서 순서가 섞이도록 하는 방법입니다.
가장 단순하지만, 실제로 사용해 보면 인접한 숫자들이 순서대로 몰리는 경우가 자주 발생해서 랜덤성이 다소 떨어지는 단점이 있습니다.
simpleShuffle = (arr) => arr.sort(() => Math.random() - 0.5);
console.table(simpleShuffle(arr))
2. 정렬(Sort)과 맵(Map)으로 구현
가장 단순하고 심플한 방식입니다. 코드가 간결하고 짧지만 배열 순회를 2번(Map), 그리고 정렬(Sort)을 하기 때문에 속도가 다소 느린 단점이 있습니다.
- map()으로 [{key: 랜덤값, val: 배열값},...] 배열 생성
- key 값(랜덤값)으로 정렬해서 배열 섞기
- map()으로 배열값만 가진 배열을 반환
const arr = [1,2,3,4,5,6,7,8,9,10,11,12]
const shuffledDeck = (arr) =>
arr.map((val) => ({ key: Math.random(), val: val }))
.sort((x, y) => x.key - y.key)
.map((card) => card.val);
console.table(shuffledDeck(arr));
3. 피셔-예이츠(Fisher–Yates) 셔플 알고리즘으로 구현
랜덤성을 확보할 수 있는 최적의 카드 섞기 알고리즘을 만든 두 사람의 이름을 따서 만든 알고리즘입니다.
이론에 대한 설명음 다음 위키피디아 페이지를 참고하면 됩니다.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
현재 우리가 사용하는 피셔-예이츠 알고리즘은 리처드 더스텐펠트(Richard Durstenfeld)라는 사람이 개선한 최신의 알고리즘입니다.
배열 순회를 한 번만 해서 섞기가 완료되기 때문에 속도가 빠르고, 랜덤성도 유지됩니다.
가장 많이 사용하는 카드 섞기 알고리즘 중의 하나입니다.
- 루프문으로 배열 길이만큼 역순으로 배열 값 1번 순회하면서 2->3을 반복
- 순회하는 현재 요소 인덱스보다 작은 인덱스를 랜덤으로 선택
- 현재 인덱스의 배열 값과 랜덤 위치의 배열 값을 상호 교환
2번의 현재 배열 인덱스 위치보다 작은 배열 요소들 중에서 위치를 랜덤으로 선택하는 게 핵심입니다. 한번 랜덤 값이 확정된 배열 요소는 바뀌지 않는 특징을 가지고 있습니다.
셔플 하지 않은 배열 요소들 중에서만 임의로 교환할 값을 선택하기 때문에 랜덤성이 충분히 유지되는 장점이 있습니다.
최신의 파생 카드 섞기 알고리즘들의 바탕이 되는 알고리즘입니다.
const fyShuffle = (arr) => {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor((i + 1) * Math.random());
[arr[i], arr[j]] = [arr[j], arr[i]]; // 배열 값 교환
}
return arr;
};
console.table(fyShuffle(arr))
