Friday, April 22, 2011
Stochasm Addict
Blog Entry #212
We return now to our discussion of HTML Goodies' "JavaScript and HTML Tricks" tutorial. In our last episode, we stored a multiline list of domain names in the value of a domains hidden control and then converted that value to a lexicographically sorted domainList array. We're ready to move on to the tutorial's Randomizing Data with JavaScript section, which presents a short script for randomly ordering domainList's values.
randomComparison = function (a, b) {
return Math.random( ) - 0.5; }
domainList.sort(randomComparison);This code is to be substituted for the
domainList.sort( ); line in the Getting Data From Text Lines in Hidden HTML Elements script. Subsequently, a showList(domainList); command displays the randomized domainList à la the lexicographic domainList.Here's what the author has to say about the randomization code:
The comparison function returns a value greater than zero or less than zero depending on which element should be sorted first. When the sorting algorithm is executed the data will be randomized if the comparison function gives each comparison of elements an equal probability of being greater than zero or less than zero.The second sentence is OK but the first sentence has the cause and effect of the comparison function reversed - it should read: "The comparison function returns a value greater than zero or less than zero, and that return, in turn, determines whether a given array value x is given a lower or higher array index than another value y to which x is being compared." But perhaps we should back up and begin at the beginning, so to speak.
sort( )ing with a comparison function
We are used to seeing functions act on strings, numbers, and objects. Somewhat unusually, the sort( ) method of the core JavaScript Array object can optionally input a function that directs the sorting process. sort( ) calls this function, and feeds to it two array values to be compared, over and over again in a looplike manner until the sort is complete.
The sort( ) function parameter can take the form of a pointer to the function
arrayObject.sort(functionReference);or be a function declaration itself.
arrayObject.sort(function (a, b) { ... });It's not necessary to explicitly call the comparison function: sort( ) does that automatically (imagine there's a
ValuePairObject.oncompare = functionReference;association statement in the code).
Most comparison functions act on their arguments[0] and arguments[1] values in some way, and it is common practice to parameterize those values respectively with a and b identifiers - cf. the illustrative examples in JavaScript Kit's "Sorting a JavaScript array using array.sort( )" tutorial. Conversely, if a comparison function does not act on its arguments, as is the case for the "JavaScript and HTML Tricks" randomComparison function, then the a/b parameters can be left out.
The relationship between the return of the comparison function and the resulting relative array indexes of two compared values x and y is detailed in the Description section of Mozilla's sort( ) page. Recalling that the random( ) method of the core JavaScript Math object returns a pseudo-random floating-point number ranging from 0 (inclusive) to 1 (exclusive), here's how that relationship relates to the randomComparison function:
• If
Math.random( ) - 0.5 gives a negative number, then the a value will be placed earlier (given a lower array index) than the b value in the new domainList. In the showList( ) join( ) display, a will appear higher than b.• If
Math.random( ) - 0.5 gives a positive number, then the a value will be placed later (given a higher array index) than the b value in the new domainList. In the showList( ) join( ) display, a will appear lower than b.(It is possible for
Math.random( ) - 0.5 to give exactly 0, in which case Mozilla recommends that user agents leave a and b unchanged with respect to each other, but sorted with respect to all different elements,but the odds of this happening are too small to worry about.)
The randomized domainList display can be seen at the WebReference version of the tutorial but is once again throttled at the HTML Goodies version by the braces-and-square-brackets-shouldn't-be-escaped problem identified in the previous post. Here's what you should see - the display is augmented with a button for your convenience.
Result
Just like shuffling an iTunes track list, eh?
The modified randomComparison function below offers some insight into the sorting process:
var count = 0;
randomComparison = function(a, b) {
count++;
var x = Math.random( ) - 0.5;
if (x <= 0) { a = a + " (L)"; b = b + " (H)"; } /* (L) is for Lower index, (H) is for Higher index. */
else { a = a + " (H)"; b = b + " (L)"; }
document.write("(" + count + ") " + a + ", " + b + ", " + x.toFixed(3) + "<br />");
return x; }Sample output:
(1) 123abc.us (L), 0011.us (H), -0.112
(2) 1mans.com (L), 0011.us (H), -0.251
(3) 1mans.com (L), 123abc.us (H), -0.215
(4) hesbest.com (H), 123abc.us (L), 0.234
(5) hesbest.com (H), 0011.us (L), 0.472
(6) 9900.us (L), 123abc.us (H), -0.134
...
As tallied by the count variable, randomComparison typically runs for 40-50 iterations; each output line above summarizes one iteration. In general, an initial order is established for the first three domain names in the unsorted domainList (0011.us, 123abc.us, and 1mans.com) and then the remaining domain names are 'played off' against that order.
The Randomizing Data ... section concludes with some technical remarks on sorting algorithms that are of limited use to the weekend silicon warrior, but there is one sentence in those remarks that I wanted to comment on:
As far as I know, Safari is the only browser which may have an unstable sorting algorithm, resulting in the domain uuuuu.us being sorted to the last position most of the time, although other domains appear to be randomly placed.I can't vouch for other platforms, but on my iMac uuuuu.us isn't sorted to the domainList[15] position any more often than any of the other domain names when using Safari.
I was going to discuss the tutorial's "fieldset" topic in this post, but I've changed my mind - let's deal with it next time.
reptile7
- posted by A. Peak @ 3:14 PM
Actually, reptile7's JavaScript blog is powered by Café La Llave. ;-)