Jump to content

js-tutorial array sorting - sorting randomly


celus

Recommended Posts

Hi everybody
If I'm right, the JS-Tutorial about sorting arrays randomly has a lack. The order of the array is kind of in a random order at the first glance, but the elements often stay at the same place as they were. This is true in the most for the element at the end of the array and the effect happens in most browsers, but not in all of them. I've written a script to test this. In these browsers the elements are not evenly distributed as they should: Chrome, IE, Edge, Opera. In Safari they were evenly distributed when I tried it. Try it yourself.

<!DOCTYPE html>
<html>
<body>
<p id="demo"></p>
<script>
var sum;
var points;
var i, j;
sum    = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
for (i=0;i<1000;i++){
 points = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1];
 points.sort(function(a, {return 0.5 - Math.random()});
 for (j=0;j<points.length;j++){
  sum[j]+=points[j];
 }
}
document.getElementById("demo").innerHTML = sum;
</script>
</body>
</html>
What the code does: It creates an array with a leading 1 and a 1 at the last place and zeroes between (points). Then it sorts this array randomly and adds the resulting array to a sum array. Then it starts again with the specific array. The generating, sorting and adding is done a 1000 times. When you reload the page the summed up numbers are displayed.
Result: In many browsers the last number is higher than the others, which shouldn't happen with correct random sorting.
Cheers,
celus
  • Like 1
Link to comment
Share on other sites

It seems that you are complaining that Math.random() is not truly random. I'm sure it isn't. The distribution does look fairly flat... The flatness can be examined with a simple test program...

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Math.Random()</title>
</head>

<body>
<p>Math.random</p>
<div id="out"></div>

<script>
'use strict';
    var a = [];
    for (var i=0 ; i<100 ; i++){
       a[i] = 0;
    }
    for (var i=0 ; i<1000000 ; i++){
       var x = Math.random();
       var n = Math.floor(x*100.0);
       //alert(n);
       a[n]++;
    }
    var str = "";
    for (var i=0 ; i<100 ; i++){
       str += i + " : " + a[i] + "<br/>";
    }
    document.getElementById("out").innerHTML = str;

</script>

</body>
</html>

However it certainly is NOT considered random enough for cryptography.

 

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random

  • Like 1
Link to comment
Share on other sites

You should repeat the experiment 20 or 30 times, and I would go with 1000000 iterations instead of 1000. If you don't do this, the results don't have statistical significance and may just be a coincidence. You should declare the function outside of the loop to make the code more efficient, otherwise it may not be able to handle 1000000 iterations.

 

Other than that, pseudo-random numbers generally are not random enough for scientific application.

Link to comment
Share on other sites

Hi everybody

 

I'm not saying the Math.random() function isn't random enough.

 

(I should have posted my text under suggestions.)

 

I think the different browsers have different sorting algorithms in the background.

Even if the random number generator is good, the sorting algorithm of most browsers doesn't treat all numbers in the array the same. As it seems to me, in most browsers the last element of the array is inserted/sorted last. Now if we define the sorting function e.g. as a < b, if the last element in the array is the smallest, it moves through the whole array. But if we define it as Math.random()<0.5, it is unlikely that the last element will move far from its place. Of course this depends on the sorting algorithm in the background. That's why I tested it with different browsers. Of course I executed my script many times. If the sorting is tested for 100'000 times, the results show the same problem.

Link to comment
Share on other sites

Hmm, when testing in Firefox and Chrome I don't see the issue, it seems to be pretty random to me.

 

This is the code I tested, it seems perfectly random, even when I increased the iterations to 10,000,000

var points = [1, 0, 0, 0, 0, 0, 0, 0, 1];
var a, i, j
var result = [0, 0, 0, 0, 0, 0, 0, 0, 0];
for(i = 0; i < 1000000; i++) {
  a = points.sort(s);
  for(j = 0; j < a.length; j++) {
    result[j] += a[j];
  }
}

document.getElementById("demo").innerHTML = result.join(", ");
function s(a, B){return 0.5 - Math.random()}
Link to comment
Share on other sites

Hello

 

Thanks for your answer. The script you posted shows an equal distribution, that's true. I tried changing it the following way to spot the difference of your script and mine: I moved the line var points = ... in the loop:

 

 

 
var a, i, j
var result = [0, 0, 0, 0, 0, 0, 0, 0, 0];
for(i = 0; i < 1000000; i++) {
  var points = [1, 0, 0, 0, 0, 0, 0, 0, 1];
  a = points.sort(s);
  for(j = 0; j < a.length; j++) {
    result[j] += a[j];
  }
}
document.getElementById("demo").innerHTML = result.join(", ");
function s(a, {return 0.5 - Math.random()}
 

 

It seems in the line

a = points.sort(s);

the Array points gets changed. I wanted to reset it every time the outer loop repeates itself.

Edited by celus
Link to comment
Share on other sites

I see, that's right, the sort() method is modifying the source array itself, I had forgotten about that. The points array should be reset on each iteration.

 

When I do that, it does seem that the last position has the most probability of staying the same. I also notice that positions furthest from the 1 on the left have less change of getting a value. It seems the sorting algorithm is unlikely to move an element far from its starting position.

Link to comment
Share on other sites

It seems the sorting algorithm is unlikely to move an element far from its starting position.

 

 

If I was sorting a deck of cards or something like that I would never use this approach -- so what is the interest or usefulness?

 

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...