배열을 무작위로 섞는 가장 효율적인 알고리즘, Fisher-Yates 알고리즘

(js로 알고리즘을 작성하였습니다.)

 

Fisher-Yates 알고리즘이란 배열을 무작위로 섞기 위한 알고리즘 중 가장 효율적인 방법 중 하나입니다.

 

이 알고리즘은

 

1.배열의 마지막 인덱스부터 시작하여 0번 인덱스까지 반복하면서

 

2.각 인덱스의 값과 무작위로 선택한 다른 인덱스의 값 위치를 서로 바꾸는

 

방식으로 동작합니다.

 

예를들어 다음과 같은 배열이 있다고 가정해 봅시다.

 

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

 

Fisher-Yates 알고리즘을 적용하면 다음과 같이 배열의 인덱스를 무작위로 섞어가며 배열을 섞을 수 있습니다.

 

1.마지막 인덱스부터 시작하여 0번 인덱스까지 반복합니다.

2.현재 인덱스(i)와 0부터 현재 인덱스(i)까지 무작위로 선택한 다른 인덱스(j)의 값을 서로 바꿉니다.

 

// Fisher-Yates 알고리즘을 적용하여 배열을 섞음
for (let i = arr.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

console.log(arr); // [5, 2, 3, 1, 4] (무작위로 섞인 배열)