Random Sort

무작위 퀴즈를 구현하는 과정에서 random 하게 문제를 섞어야 했다.

 

random sort를 구현함에 있어서 처음에는 sort함수를 통해 다음과 같이 정렬하는 로직을 구상했었다.

function shuffle(arr) {
  arr.sort((a, b) => Math.random() - Math.random());
}

하지만 이 정렬 방식에는 약간의 문제가 있다.

 

예를 들어 1, 2, 3이 담긴 배열을 정렬한다고 할 때 다음과 같은 결과가 나온다.

let arr = [1, 2, 3];

function shuffle(arr) {
  arr.sort((a, b) => Math.random() - Math.random());
}

// 나올 수 있는 경우의 수를 count한다.
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("")]++;
}

console.log(count);

결과를 보니 랜덤 하게 나오긴 하지만, 경우에 따라 나오는 빈도 수의 차이가 고르지 않고 차이가 많이 발생한다.

 

모든 경우의 수가 비슷한 정도로 나오게 하기 위해서는 새로운 로직이 필요하다.

가장 대표적인  random sort 알고리즘은 Fisher-Yates Shuffles라는 알고리즘이다.

 

간단하게 설명하면 무작위로 index 값을 뽑아 배열의 끝부터 채워가는 알고리즘이다.

코드로는 다음과 같이 작성할 수 있다.

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
  	// 무작위로 index를 추출
    let j = Math.floor(Math.random() * (i + 1));
    
  	// 선택된 index와 가장 맨 끝의 문자를 교환
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

새로운 shuffle 메서드로 결과 값을 확인해보면

이전 sort 함수를 활용해 랜덤 하게 섞은 결과와는 확연하게 균등한 결과가 나온 것을 확인할 수 있다.

 

## Reference

배열 요소 무작위로 섞기

Fisher–Yates shuffle - Wikipedia