JavaScript study notes: Random sorting of arrays_javascript skills

Recommended reading: JavaScript Study Notes Array Sum Method

Add, delete, modify and check arrays of JavaScript study notes

JavaScript provides sort() and reverse() methods to reorder array items. But many times these two methods cannot meet the needs of our actual business, such as random shuffling in poker games.

In this article, let’s learn how to achieve the effect of the above example, as well as some related knowledge about random sorting of arrays.

I checked the relevant information about random sorting of arrays on the Internet, and I saw Math.random(). Open the browser controller and enter:

Math.random()

As can be seen from the picture, Math.random() obtains a random number between 0 and 1. As we all know, sort() can call a function as a parameter. If the function returns a value of -1, it means that item a in the array is ranked before item b. In this way, you can write a random function to compare the number randomly generated by Math.random() with 0.5. If it is greater than .5, it will return -1 (a is ranked in front of b), otherwise it will return 1 (b is ranked in front of a):

function randomSort(a, b) {
return Math.random() > 0.5 ? -1 : 1;
}

Look at an example:

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort(randomSort);

In this way, the example effect at the beginning of the article can be achieved:

Although the previous method achieves random sorting of the array, it always feels that the position of each element sent to the new array is not random. Just like the previous example, the element with value 1 in array arr has its original key value 0. After random sorting, the probability of the key value 1 being 0-8 is the same. Then it is decreasing here because the sort() method compares sequentially.

To address this phenomenon, we can use the following recursive method to deal with it:

function randomSort(arr, newArr) {
// 如果原数组arr的length值等于1时，原数组只有一个值，其键值为0
// 同时将这个值push到新数组newArr中
if(arr.length == 1) {
newArr.push(arr[0]);
return newArr; // 相当于递归退出
}
// 在原数组length基础上取出一个随机数
var random = Math.ceil(Math.random() * arr.length) - 1;
// 将原数组中的随机一个值push到新数组newArr中
newArr.push(arr[random]);
// 对应删除原数组arr的对应数组项
arr.splice(random,1);
return randomSort(arr, newArr);
}

In this case, we can use it like this:

for (var i = 0; i < 10; i++) {
var arr=[1,2,3,4,5,6,7,8,9];
var newArr=[];
randomSort(arr,newArr);
console.log(newArr);
}

Output result:

After executing the randomSort(arr, newArr) function, the original array arr is cleared.

If you use this method to do the shuffling example at the beginning of the article, you need to reset the pukePic array in the resetPic() function:

In addition to the above two methods, @Traveller shared an article "Implementation of Randomized Sorting Algorithm for Array Elements" on DIV.IO. This article provides three implementation methods for random sorting of array items:

Use the array sort method to randomly sort the array elements

Array.prototype.shuffle = function(n) {
var len = this.length ,
num = n ? Math.min(n,len) : len,
arr = this.slice(0);
arr.sort(function(a,b){
return Math.random()-0.5;
});
return arr.slice(0,num-1);
}

Randomly swap elements in the array

lib = {}
lib.range = function(min,max) {
return min + Math.floor(Math.random()*(max-min+1));
}

Array.prototype.shuffle = function(n) {
var len = this.length,
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
temp,
index;
for (var i=0;i<len;i++){
index = lib.range(i,len-1);
temp = arr[i];
arr[i] = arr[index];
arr[index]=temp;
}
return arr.slice(0,num);
}

Randomly extract an element from the original array and add it to the new array

lib = {}
lib.range = function(min,max) {
return min+Math.floor(Math.random()*(max-min+1));
}
Array.prototype.shuffle = function(n) {
var len = this.length, 
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
result=[],
index;
for (var i=0;i<num;i++){
index = lib.range(0,len-1-i);
// 或者 result.concat(arr.splice(index,1))
result.push(arr.splice(index,1)[0]);
}
return result
}

Shuffling algorithm

The basic principle of random sorting of arrays is the shuffling algorithm (Fisher–Yates shuffle):

is an algorithm that disrupts the order of finite sets

Principle

Define an array (shuffled), the length (length) is the length of the original array (arr)
Take 0 to index (initial 0) random value rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr[index]
index++ ; Repeat step 2 until index = length -1
It is the assignment process of shuffled from 0 to length-1, and the newly added value is arr[index]. The value of shuffled[index] is the random value shuffled[rand] among the assigned elements, because there will be two duplicates. value, so shuffled[rand] is equal to the newly added value arr[index]

shuffle method in underscore.js

function random(min, max) {
if (max == null) {
max = min;
min = 0;
}
return min + Math.floor(Math.random() * (max - min + 1));
};
function shuffle(arr) {
var length = arr.length,
shuffled = Array(length);
for (var index = 0, rand; index < length; index++) {
rand = random(0, index);
if (rand !== index) shuffled[index] = shuffled[rand];
shuffled[rand] = arr[index];
}
return shuffled;
}

Practical application:

var arr = [1,2,3,4,5,6,7,8,9];
for (var i = 0; i < 10; i++){
console.log(shuffle(arr));
}

The results output by Chrome are as follows:

Similarly, use the shuffling algorithm to complete the example at the beginning of the article:

There is also a simpler and easier to understand way of writing:

function shuffle(arr) {
var i, 
j,
temp;
for (i = arr.length - 1; i > 0; i--) {
j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};

Summary

This article mainly summarizes and collects relevant information about random sorting of arrays. Of course, there are many ways to achieve similar functions in the market. These are just collected and organized here. If you have a better method, please share it with us in the comments.

The above content is an introduction to the random sorting of arrays in JavaScript study notes introduced by the editor. I hope it will be helpful to you!