배열 무작위 섞기 (셔플)

 

배열을 섞을 수 있는 메서드를 만들어보자. 

 

 

1. 기존 배열 값은 바꾸지 않는다. (복사해서 사용)

2. 메서드를 실행할 때마다 무작위로 섞인다. 

 

<script>

    const array1 = [1, 2, 3, 4, 5, 6, 7, 8];
    console.log("array1", array1);
    const shuffled1 = shuffleArray(array1);
    console.log("shuffled1", shuffled1);
    
    const array2 = ['기린', '사자', '토끼', '원숭이', '강이지', '고양이'];
    console.log("array2", array2);
    const shuffled2 = shuffleArray(array2);
    console.log("shuffled2", shuffled2);

    function shuffleArray(element){
      const array = element.concat();
      
      const arrayLength = array.length;

      for( let i = arrayLength-1; i >= 0; i--){
        const randomArray = Math.floor(Math.random() * (i+1));
        [array[i], array[randomArray]] = [array[randomArray], array[i]];
      }
      return array;
    }

  </script>

 

 

 [ array [ i ], array [randomArray]] = [array [randomArray], array [ i ] ]

피셔 예이츠(Fisher Yates) 알고리즘을 사용하며, 재사용할 수 있도록 처리 작업을 함수로 만든다.

 

 

※ 피셔 예이츠 알고리즘 

 

 [ array[ i ], array [randomArray]] = [array [randomArray], array [ i ] ]

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

for문 i에 4, 3, 2, 1, 0 을 대입했을 때  Math*random()은 0 이상 1 미만의 값이 반환되므로 randomArray는 0 이상 i이하의 값을 갖게 된다. 

 

결과

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

 

 ※ Point

 

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

 

REF:

피셔-예이츠 셔플 - 위키백과, 우리 모두의 백과사전