자바스크립트에서 배열 섞기 알고리즘 (피셔-예이츠 셔플)

배열을 랜덤으로 섞어야 하는 알고리즘의 구현을 해보기로 했다.

조사결과 피셔-예이츠 셔플이라는 알고리즘 방법을 알게되었고, 이를 자바스크립트로 구현하기로 하였다.

조건은 다음과 같이 설정하였다.

inputs : 임의의 길이를 가진 배열 arr, 임의의 배열 arr의 길이 n
output : 임의의 배열 arr이 무작위로 섞인 새로운 배열 shuffledArr

실제 구현은 다음과 같이 하였다.

const shuffle = (arr, n) => {
  const shuffledArr = [...arr];
  for(let i = 0; i < n - 1; i++) {
    // i ≤  < n인 임의의 정수 (최소값이 i, 최대값이 n - 1)
    const randomIdx = Math.floor(Math.random() * ((n - 1) - i + 1)) + i;
    [shuffledArr[i], shuffledArr[randomIdx]] = [shuffledArr[randomIdx], shuffledArr[i]]
  }
  return shuffledArr;
}

 

https://ko.wikipedia.org/wiki/%ED%94%BC%EC%85%94-%EC%98%88%EC%9D%B4%EC%B8%A0_%EC%85%94%ED%94%8C

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