Why is your array not out of order enough?

“This is the 17th day of my participation in the First Challenge 2022.

preface

It’s easy to get an array out of order, right?

Given an array such as [1,2,3,4], how do you implement out-of-order ordering? Arr.sort (() => math.random () -0.5) : arr.sort(() => math.random () -0.5) This example comes from JavaScript topics out of order.

But it’s not enough of a mess, and what’s not enough of a mess is that every number is not equally likely to be in every position, as we’ll see later.

In fact, when I first saw this implementation, I had a question: why is the sort parameter still a variable value?

With this question in mind, I re-read MDN’s API explanation of SORT.

sort

The sort() method sorts the elements of an array using an in-place algorithm and returns the array. The default sort order is built when converting elements to strings and then comparing their UTF-16 code unit value sequences

Because it is implementation-dependent, the temporal and spatial complexity of sorting cannot be guaranteed.

arr.sort([compareFunction])
Copy the code

• compareFunctionoptional
• Used to specify functions that are sorted in a certain order. If omitted, the element is sorted by the Unicode loci of each character in the converted string.

- 'firstEl' the first element used for comparison. - 'secondEl' The second element used for comparison.Copy the code

I learned at least three very valuable pieces of information:

1. Different browser vendors have different algorithms for implementing sort, because ECMA only describes the effects and does not restrict how they can be implemented.

2. SortcompareFunction takes two arguments firstEl, secondEl, and arr.sort((a, b) => a-b). SortcompareFunction takes two arguments firstEl, secondEl. Therefore, it is equivalent to the sorting process of jengge is pin-two digit comparison, we can achieve the purpose of out-of-order by dynamically switching the sorting rules (forward order, reverse order).

See if it’s messy enough

As mentioned above, such disorder may not achieve the desired effect. So let’s write a way to verify that.

function randomArr(arr) {
    arr.sort(() = > Math.random() - 0.5);
    return arr;
}

const TestCount = func= > {
    const times = 10000000;
    const count = new Array(4).fill(0).map(() = > new Array(4).fill(0));
    for (let i = 0; i < times; i++) {
        func.call(null[0.1.2.3,]).forEach((n, i) = > count[n][i]++);
    }
    console.table(count.map(n= > n.map(n= > (n / times * 100).toFixed(2) + The '%')));
};

TestCount(randomArr)

Copy the code

Current Execution environment: Google Chrome 98.0.4758.80 (official version) (x86_64)

It can be seen that such out-of-order method cannot guarantee the average probability of each number in each position. The higher probability is on the diagonal. Which means it’s more likely to be in its original position.

What causes numbers to appear more often in their original positions? Let’s find out.

Insertion sort

If you want to get to the bottom of the problem, you have to understand how sort works, but ECMAScript only specifies the effect, not the implementation, so different browsers implement it differently.

To solve this problem, let’s take V8 as an example. V8 uses insertion sort when the target array length is less than 10; Instead, use a mixture of quicksort and insert sort.

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element; }};Copy the code

Let’s assume arrays of [1,2,3] to analyze the process layer by layer.

Note that sort is implemented by InsertionSort. The value of InsertionSort is 0 and the value of to is 3.

Insertion sort assumes that the first element is ordered, so I starts at 1.

1. I = 1, at this timeComparefn (1,2)There’s a 50% chance that 2 and 3 won’t change position and return[1, 2, 3], with a 50% chance of returning,1,3 [2].
2. I = 2, we make another analysis, the value of A [I] is 3, then the inner layer cycle comparisonComparefn (2,3)Return [1,2,3] and the comparison ends.

With a 50% chance of becoming [1,3,2], j– has not found the correct position for 3, and comparefn (1,3) will return [1,3,2] and [3,1,2] again with a 50% chance.

Therefore, the following table can be obtained by synthesis

Implement more chaotic disorder

Fisher – Yates

Iterate over the number group, pick a random number and swap positions with it.

function shuffle(a) {
    for (let i = a.length - 1; i; i--) {
        let j = Math.floor(Math.random() * (i+1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}
Copy the code

My method

My initial idea was to take a random bit of an array and stuff it into a new array and return the new array.

Let’s write an example to test this approach:

const n = 100000;
// Count the number of occurrences at each position
const count = new Array(5).fill(0)
for(let i = 0; i < n; i++) {
    const arr = [1.2.3.4.5];
    const newArr = [];
    while(arr.length) {
        newArr.push( (arr.splice(~~(Math.random() * arr.length), 1) [0])); } count[newArr.indexOf(1)] + +; }console.log(Number of occurrences of '1 at each position: ', count)
Copy the code

So you can see that the number of 1’s in every position is about the same, so it works that way.

conclusion

Maybe you have a better way of doing this, so leave your answer in the comments section.

Point ⭐️ support, exchange growth together.