CODEWITHSUNDEEP
javascriptsortingcross-browser
Janaaaa
Janaaaa

Reputation: 1416

Inconsistent results between different browsers with my Javascript code for randomizing a list

I got this piece of code from a website for randomizing a list of items. [This is for a music player that randomizes the songs (list) in every new visit by the user, thus not boring them by starting with the same song that they heard in the past visit]

    $(document).ready(function(){
      $('ul').each(function(){
            // get current ul
            var $ul = $(this);
            // get array of list items in current ul
            var $liArr = $ul.children('li');
            // sort array of list items in current ul randomly
            $liArr.sort(function(a,b){
                  // Get a random number between 0 and 10
                  var temp = parseInt( Math.random()*10 );
                  // Get 1 or 0, whether temp is odd or even
                  var isOddOrEven = temp%2;
                  // Get +1 or -1, whether temp greater or smaller than 5
                  var isPosOrNeg = temp>5 ? 1 : -1;
                  // Return -1, 0, or +1
                  return( isOddOrEven*isPosOrNeg );
            })
            // append list items to ul
            .appendTo($ul);            
      });
});

This works perfectly fine when I open my site in Chrome browser. The sorting is done pretty heavily and hence I could see that the list is randomized to a great extent.

But in Firefox and IE, the sorting is not happening to a good extent. I see that the first list item remains first in 7 out of 10 tries. And I could see the same for many other items. Ex: Item #5 occur in 3rd position in 5 out of 10 tries. With these observations, I could tell that the JS code is not working properly in IE and Firefox. (may be due to the way different browsers treat JS code because of the differences in the engine)

Now, Is there anything I can change in the JS code to make it work in all browsers?

Or Is there any other better sorting algorithm that would do a decent sorting in all browsers when implemented using JS?

I understand that a part of my 2nd question has been answered in other questions within SE but I couldn't find about the 'browser compatibility' part in those questions.

Thanks for helping.

Upvotes: 1

Views: 1349

Answers (3)

Bergi
Bergi

Reputation: 665020

Your randomisation is not very good:

// Get a random number between 0 and 10
var temp = parseInt( Math.random()*10 );
// Get 1 or 0, whether temp is odd or even
var isOddOrEven = temp%2;
// Get +1 or -1, whether temp greater or smaller than 5
var isPosOrNeg = temp>5 ? 1 : -1;
// Return -1, 0, or +1
return( isOddOrEven*isPosOrNeg );

That means in a half of the cases you return 0, which tells the sort function that the two items are equal. A good sort function will notice that and not ask again. With only a few items, you have a very high chance of the items not getting sorted well. You can proof this by counting (logging) how often your compare-function is called.

Also you don't need to return only +1, 0 or -1, you can just return any positive or negative number (see also below). For randomizing, you never really need to return equality. So, use this instead:

….sort( function() {
     return 0.5 - Math.random(); // that would be enough!
} );

However, one should not use sort for randomisation at all. Math.random does not lead to a total ordering, and sort is not made for that: (from the EcmaScript specification)

If comparefn is […] not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.

A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0.

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b.

  • Calling comparefn(a,b) does not modify the this object.
  • a =CF a (reflexivity)
  • If a =CF b, then b =CF a (symmetry)
  • If a =CF b and b =CF c, then a =CF c (transitivity of =CF)
  • If a <CF b and b <CF c, then a <CF c (transitivity of <CF)
  • If a >CF b and b >CF c, then a >CF c (transitivity of >CF)

NOTE: The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered.

An optimised sort function can easily screw up if these properties are not fulfilled. That can mean no sorting at all as well as never terminating sorting. See Is it correct to use JavaScript Array.sort() method for shuffling?

Instead, use a standard shuffle algorithm, there are many good ones. The Fisher-Yates-Shuffle is really simple to implement for example, see the question How to randomize (shuffle) a JavaScript array?.

Upvotes: 3

ebsddd
ebsddd

Reputation: 1026

The problem is the shuffling method. An easy but still wrong way to fix it is change the whole sort function to return Math.random() < 0.5 ? 1 : -1;. But that isn't guaranteed to randomize the list properly (an element will move up with a probability of 50%, whereas in a true shuffle it will move up with a probability proportional to the number of elements originally above it).

The correct thing to do is implement a Fisher-Yates shuffle. This is also O(n) rather than O(n log n).

Upvotes: 1

LPD
LPD

Reputation: 2883

The problem is the input in this case.

parseInt( Math.random()*10 ) returns an even number all the time, thus taking your randomising function for a toss.

Something similar I found in this link. Hope it also helps.

In Safari and I think also IE7 and 8 Math.random() is NOT random?

Upvotes: 1

Related Questions