받아 온 배열 형태의 데이터 순서를 무작위로 섞고 싶어서 알게 된 Fisher-Yates Shuffle 알고리즘에 대한 글
Fisher-Yates Shuffle 알고리즘이란?
리스트나 배열의 요소를 무작위로 섞는 알고리즘이다.
효율적이고 공정하게 요소를 랜덤으로 섞는 상황에서 유용하게 쓰인다고 한다!
(예를 들어, 카드 섞기나 게임의 랜덤 이벤트 등 랜덤으로 섞는 이벤트에 유용하게 쓸 수 있다 함)
이 알고리즘의 작동 방식은 어떨까?
- 리스트의 마지막 요소부터 시작하여 각 요소를 랜덤하게 선택된 앞쪽 요소와 위치를 교환한다.
- 마지막 요소부터 시작하여 첫 번째 요소까지 이 과정을 반복해서 모든 요소가 무작위로 섞일 수 있게 한다.
코드 예시와 함께 이해해보자
fisherYatesShuffle 함수를 정의해본다고 하자
이 함수에는 매개 변수로 arr(배열)을 받는다
이 배열이 무작위로 섞이는 수를 제한하기 때문에 루프를 돌린다
이 알고리즘은 마지막 요소부터 시작해서 각 요소를 랜덤하게 선택된 앞쪽 요소와 위치를 교환한다고 했다.
그래서 처음 시작을 let i = arr.length - 1;로 정의한다.
그 다음 i > 0;으로 정의해준다.
왜 i = 0이 아닌 i > 0일까?
각 요소는 마지막 요소부터 시작해 랜덤한 인덱스와 위치를 바꾸는데, i = 1일 때는 교환할 요소가 하나밖에 남지 않는다.
그래서, i = 0일 때는 교환할 요소가 남지 않는 것이기에 i > 0로 정의해주는 것이다.
그 다음, 0부터 i까지의 인덱스 중 무작위의 랜덤숫자를 생성한다.
Math.floor와 Math.random을 사용하여 랜덤 숫자를 만들 수 있다.
여기의 Math.random() * (i + 1)에서 i에 1을 더해주는 이유는 이 random 메소드가 0부터 i까지의 정수를 잘 반환하기 위함이다.
1을 더해주지 않으면 0부터 i 전의 숫자까지만을 반환하기 때문이다.
다음으로 이 랜덤숫자와 현재 루프를 돌리고 있는 숫자의 인덱스 요소들을 서로 교환해준다.
그럼 이 루프가 끝날 때까지 계속해서 서로 요소들이 섞이게 되는 것이다.
예시 함수의 전체
이 알고리즘을 어떻게 내 프로젝트에서 사용했냐면 아래 코드와 같다
(어라 async가 왜 붙어있지 지워야겠다 저건 무시해주세요..ㅠ)
코드를 보면, 위의 예시처럼 매개 변수로 array를 받지만 나는 API 요청을 받아온 데이터를 랜덤으로 섞을 예정이었다.
데이터 자체를 바꿔서 리턴 할 수 없으므로, 스프레드 연산자를 이용하여 duplicate을 해줬다.
나머지 코드는 위의 예시와 같고, 리턴은 duplicatedArray로 해줬다.
이렇게 이 알고리즘을 통해서 리스트나 배열의 요소들을 랜덤으로 섞을 수 있게 되었다 :)
