Fisher-Yates 셔플 알고리즘
이 알고리즘은 배열의 요소를 섞는 것입니다. 배열의 요소를 섞기 위해 자체 논리를 작성할 수 있지만 많은 개발자는 F 아이셔-예이츠 최신 셔플 알고리즘은 배열의 요소를 섞는 가장 좋은 방법입니다. 이 알고리즘에는 다음과 같은 단계가 있습니다.
따라야 할 단계
- 이 알고리즘에 따르면 배열을 뒤에서 앞으로 반복해야 합니다. 예를 들어, 다음 예에서 인덱스 0에서 인덱스 7까지 8개의 요소(A,B,C,D,E,F,G,H)로 구성된 배열이 있습니다. 따라서 첫 번째 루프 패스는 요소에 영향을 미칩니다. 마지막 인덱스 7은 H입니다.
- 다음 단계는 선택한 인덱스 7과 인덱스 0 사이에 임의의 숫자(임의 인덱스)를 생성하는 것입니다. 임의의 인덱스를 3이라고 가정해 보겠습니다.
- 임의의 인덱스를 얻은 후 선택한 인덱스에 있는 요소와 임의의 인덱스에 있는 요소를 교환합니다. 제공된 배열에서 임의의 인덱스에 있는 요소는 D입니다. 따라서 교환 후 배열은 A,B,C로 변경됩니다. ,H,E,G,F,D
- 두 번째 루프 패스에서는 마지막 인덱스를 무시하고(이미 루프되어 있으므로) 요소 A와 F 사이에 있는 인덱스 0과 인덱스 6 사이의 임의 인덱스를 찾습니다. 생성된 임의 인덱스를 2로 둡니다.
- 임의의 인덱스를 가져온 후 6과 2의 인덱스에 있는 요소를 교환해 보겠습니다. 이제 배열은 A,B,F,H,E,G,C,D로 표시됩니다.
- 이 알고리즘은 인덱스 6을 무시하고 인덱스 1에 도달할 때까지 인덱스 5와 인덱스 0 사이에서 임의의 인덱스를 찾기 시작하는 것과 같은 패턴을 따릅니다. 인덱스가 없기 때문에 루프에 인덱스 0을 사용할 수 없습니다. 교환 목적으로 0보다 작습니다.
- 생성된 임의의 인덱스가 루프 인덱스로 선택될 가능성이 있습니다. 예를 들어, 선택한 인덱스 4와 인덱스 0 사이에서 루프가 실행되고 있다고 가정합니다. 생성된 임의의 인덱스를 4로 둡니다. 그러면 인덱스 4의 값은 동일한 위치에 유지됩니다.
다음 예는 Fisher-Yates를 보여줍니다. 최신 셔플 알고리즘
예시
<html>
<body>
<script>
var arr = ['A','B','C','D','E','F','G','H']
var i = arr.length, k , temp; // k is to generate random index and temp is to swap the values
while(--i > 0){
k = Math.floor(Math.random() * (i+1));
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
document.write(arr);
</script>
</body>
</html> 출력
C,F,H,D,A,G,E,B // note that output will change for every iteration.