[JavaScript] 자바스크립트 배열 섞기(셔플)

060_자바스크립트 배열 섞기(셔플)

[적용]

• 게임에서 요소의 값을 섞을 때

---

[내용]

배열을 빠르면서도 고르게 섞기 위해서는 피셔 예이츠(Fisher Yates) 알고리즘이 사용된다.

다음의 샘플을 확인해보자.

const array = [1, 2, 3, 4, 5];

const arrayLength = array.length;

// 피셔 예이츠 알고리즘
for (let i = arrayLength -1; i>=0; i--) {
    const randomIndex = Math.floor(Math.random() * (i + 1));
    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];
}

console.log(array);  // 결과: [4, 5, 1, 2, 3]

 

재사용할 수 있도록 처리 작업을 함수로 만들면 편리하다.

배열을 섞는 셔플 작업이 shuffleArray() 함수에서 구현된다.

숫자 배열과 문자열 배열의 셔플 작업을 확인해 보자.

const array1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const shuffled1 = shuffleArray(array1);
console.log(shuffled1);  // 결과: [5, 1, 8, 3, ... (생략)]

const array2 = ['사자', '여우', '곰', '호랑이', '기린'];
const shuffled2 = shuffleArray(array2);
console.log(shuffled2);  // 결과: ["기린", "사자", "곰", "여우", "호랑이"]

/** 
 * 배열 셔플
 * 기존 배열 변경 없이 새로운 배열을 변환
 * @param sourceArr 기존 배열
 * @returns 셔플된 배열
 */
 
function shuffleArray(sourceArr) {
    / 기존 배열의 복제 생성
    const array = sourceArr.concat();
    // 피셔 예이츠 알고리즘
    const arrayLength = array.length;
    for (let i = arrayLength - 1; i>= 0; i--) {
        const randomIndex = Math.floor(Math.random() * (i + 1));
        [array[i], array[randomIndex]] = [array[randomIndex], array[i]];
    }
    
    return array;
}

---

[APPENDIX]

피셔 예이츠 알고리즘의 이해

5개의 요소 [0, 1, 2, 3, 4]를 가지는 배열을 생각해 보자

• for문 i에 4, 3, 2, 1, 0 대입
• Math.random()은 0 이상 1 미만의 값이 반환되므로 randomIndex는 0 이상 i 이하

 

두 가지를 주의하여 for문을 구성하면 다음과 같은 결과를 얻을 수 있다.

i	임의의 인덱스(예)	변경 후 배열(예)
4	3	[0, 1, 2, 4, 3]
3	2	[0, 4, 2, 1, 3]
2	0	[1, 3, 4, 2, 0]
1	0	[4, 1, 0, 2, 3]
0	0	[4, 1, 0, 3, 2]

 

주요 포인투는 다음의 두 가지다.

• 요소 전체가 처리 대상이 된다.
• 한번 처리된 요소는 다시 작업 대상이 되지 않는다.

 

---

 

 

 

 

 

 

참조 :
실무에 바로 적용하는 자바스크립트 코드레시피 278
아케다 야스노부, 카노 타케시 지음 / 이춘혁 옮김