[JAVASCRIPT.INFO] 셔플 알고리즘(shuffle)

셔플 알고리즘(shuffle)

Math.random() 사용해서 구현하기

function shuffle(array){
  array.sort(() => Math.random() - 0.5);
}
let arr = [1,2,3];
shuffle(arr);

Math.random() - 0.5는 양수나 음수 둘 중 하나이기 때문에 정렬 함수는 요소를 무작위로 재 정렬해준다. 그런데 sort는 이런 용도로 만들어진 메서드가 아니기 때문에 위와 같이 구현하게 된다면 1,2,3으로 만들 수 있는 순열이 같은 빈도로 나타나지 않는다.

function shuffle(array) {
  array.sort(() => Math.random() - 0.5); 
}
let count = {
  '123' : 0,
  '132' : 0,
  '213' : 0,
  '231' : 0,
  '321' : 0,
  '312' : 0,
}
for(let i=0; i<1000000; i++){
  let array = [1,2,3];
  shuffle(array);
  count[array.join('')]++;
}
for(let key in count){
  alert(`${key}: ${count[key]}`)
}

123: 375437
132: 62978
213: 124899
231: 62527
312: 62472
321: 311687

위 코드를 이용하면 결과가 한 쪽으로 쏠린다는 것을 알 수 있다. sort를 실행했을 때 내부 동작이 블랙박스 안에 담겨 있기 때문에, sort를 실행하면 이니수로 넘긴 정렬 함수가 배열을 정리해주는 데 이 과정에서 배열 요소끼리의 비교가 완전 무작위로 이루어지기 때문에 안에 무엇이 담겨있을지 더 예측하기 어려워진다. 자바스크립트 엔진마다 내부 구현 방식은 다르므로 이런 혼돈은 더 커지게 된다.

피셔-예이츠 셔플

피셔-예이츠 셔플 알고리즘은 배열 끝 요소부터 시작해 앞으로 하나씩 나아가면서 해당 요소 앞에 있는 임의의 요소와 해당 요소를 바꿔치기 하는 알고리즘이다.

function shuffle(array){
  for(let i=array.length-1; i>0; i--){
    let j= Math.floor(Math.rondom() * (i+1));        // 무작위 인덱스 (0이상 i미만)
    //array[i]와 무작위 인덱스 array[j]와 바꾼다.
    [array[i], array[j]] = [array[j], array[i]];
  }
}

피셔-예이츠 알고리즘은 "정렬" 연산이 없기에 성능상 이점도 있다.