JS 무작위 셔플링 알고리즘 배열 무작위 sorting_javascript 기술

추천 도서: JavaScript 학습 노트: 배열 추가, 삭제, 수정 및 확인

JavaScript 학습 노트 배열 합계 방식

JavaScript 학습 노트 배열 무작위 정렬

셔플링 알고리즘은 배열의 요소를 무작위로 배열하는 데 사용되는 상대적으로 생생한 용어입니다. 예를 들어, 아래 그림과 같은 배열이 있습니다. 배열의 길이는 9이고 배열의 요소 값은 1~9입니다.

위 배열부터 시작하여 우리가 해야 할 일은 배열 요소의 순서를 바꾸는 것입니다.

코드 구현

Wikipedia의 Fisher-Yates 셔플 항목은 셔플링 알고리즘에 대한 자세한 소개를 제공합니다. 아래에 설명된 알고리즘도 이론을 기반으로 작성되었습니다.

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
// and the result is...
alert(tempArray); 

위 코드에서는 배열 내의 요소를 무작위로 정렬하는 데 사용되는 shffle() 메서드를 만들었습니다. 또한 Array 객체의 프로토타입 아래에 이 메서드를 탑재하여 모든 배열에서 이 메서드를 직접 호출할 수 있습니다.

var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle(); 

작동 방식

코드를 읽은 후 이것이 배열에 어떤 역할을 하는지 살펴보겠습니다. 먼저 이 메서드는 배열의 마지막 요소를 선택합니다.

다음으로, 배열의 첫 번째 요소부터 이전 단계에서 선택한 요소까지 모두 다음 범위에 속합니다.

범위를 결정한 후 무작위로 선택된 요소가 4라고 가정하고 무작위로 숫자를 선택합니다.

그런 다음 마지막 요소와 무작위로 선택한 요소의 값을 바꿉니다.

위 교환이 완료된 후 배열의 마지막 요소에 대한 무작위 처리를 완료하는 것과 같습니다. 그런 다음 배열의 마지막 요소에서 두 번째 요소를 선택합니다.

뒤에서 앞으로 처리하는 이유는 무작위 선택 범위를 결정하기가 더 쉽기 때문입니다. 이번에는 무작위로 획득한 요소를 2:

라고 가정합니다.

그런 다음 두 번째 요소와 두 번째 요소의 값을 교환하여 두 번째 요소의 무작위 배열을 완성합니다. 그런 다음 마지막에서 세 번째 요소를 선택하고 이전 작업을 반복합니다.

나머지는 반복적인 작업이라 많이 소개하진 않겠습니다.

코드 분석

이전 섹션에서는 셔플링 프로세스를 설명하기 위해 그림을 사용했습니다. 이제 코드 자체에서 셔플링 프로세스를 살펴보겠습니다. 셔플 기능부터 시작해 보겠습니다.

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}
return input;
} 

셔플 함수는 Array 객체의 프로토타입 아래에 탑재되어 배열이 함수를 직접 호출하기 쉽습니다. shuffle 함수 내에서 이는 shuffle이 호출되는 배열을 나타냅니다.

var input = this;

위 코드에서는 셔플 함수가 호출되는 배열인 새 변수를 사용하여 이를 참조합니다. 다음으로 for 루프 내부에서 수행되는 작업을 살펴보겠습니다.

for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}

이 루프는 모든 배열의 모든 요소를 ​​반복하고 무작위 교환을 수행하는 데 사용됩니다. 순회 순서는 뒤에서 앞으로입니다. 즉, input.length-1 위치의 요소부터 시작하여 배열의 첫 번째 요소가 순회될 때까지입니다. 순회 중 위치는 변수 i로 지정됩니다.

여기서 변수 i는 위 범례에서 선택한 요소입니다.

셔플링 알고리즘

다음으로 두 줄의 코드를 사용하여 지정된 범위에서 임의의 요소를 선택합니다.

var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex];

变量 randomIndex 存储了一个随机数，该随机数可以用作数组的索引，进而提取一个随机元素。注意，该随机数的最大值并不是数组的长度，而是变量 i 的值。

确定了随机元素的索引之后，用新的变量保存该元素的值，然后交换选中元素和随机元素的值：

var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;

在这三行代码中，第一行使用新的变量保存了随机元素的值；第二行将选中元素 input[i] 的值赋给随机元素 input[randomIndex]；第三行就随机元素的值 itemAtIndex 赋给选中元素 input[i]。本质上是一个互换两个元素的值的过程，并不难理解。

至此，循环内的逻辑就介绍完了，剩下的都是重复操作。

随机性测试

上图是使用 Highcharts 制作的随机性测试图表，以可视化的方式校验本文中洗牌算法的随机性。每次刷新页面都会重新计算和生成该图表。

生成上图的数据是这样计算而来的：首先创建一个数组（上图使用的数组为 [0, 1, 2 ... 18, 19, 20]），然后使用本文中的洗牌算法重新排序，排序完成后记录每一个元素的值……以此步骤执行 100000 次，最后对同一索引位置上的数值进行求和。如此执行 10000 次之后，索引之间的总值应该相差不大。

由计算可得：

以上内容是小编给大家介绍的JS随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！