How can I reliably subsort arrays using DOM methods?

Question

UP-FRONT NOTE: I am not using jQuery or another library here because I want to understand what I’ve written and why it works (or doesn’t), so please don’t answer this with libraries or plugins for libraries. I have nothing against libraries, but for this project they’re inimical to my programming goals.

That said…

Over at http://meyerweb.com/eric/css/colors/ I added some column sorting using DOM functions I wrote myself. The problem is that while it works great for, say, the simple case of alphabetizing strings, the results are inconsistent across browsers when I try to sort on multiple numeric terms—in effect, when I try to do a sort with two subsorts.

For example, if you click “Decimal RGB” a few times in Safari or Firefox on OS X, you get the results I intended. Do the same in Chrome or Opera (again, OS X) and you get very different results. Yes, Safari and Chrome diverge here.

Here’s a snippet of the JS I’m using for the RGB sort:

sorter.sort(function(a,b){
    return a.blue - b.blue;
});
sorter.sort(function(a,b){
    return a.green - b.green;
});
sorter.sort(function(a,b){
    return a.red - b.red;
});

(sorter being the array I’m trying to sort.)

The sort is done in the tradition of another StackOverflow question “How does one sort a multi dimensional array by multiple columns in JavaScript?” and its top answer. Yet the results are not what I expected in two of the four browsers I initially tried out.

I sort (ha!) of get that this has to do with array sorts being “unstable”—no argument here!—but what I don’t know is how to overcome it in a consistent, reliable manner. I could really use some help both understanding the problem and seeing the solution, or at least a generic description of the solution.

I realize there are probably six million ways to optimize the rest of the JS (yes, I used a global). I’m still a JS novice and trying to correct that through practice. Right now, it’s array sorting that’s got me confused, and I could use some help with that piece of the script before moving on to cleaning up the code elsewhere. Thanks in advance!

UPDATE

In addition to the great explanations and suggestions below, I got a line on an even more compact solution:

function rgbSort(a,b) {
    return (a.red - b.red || a.green - b.green || a.blue - b.blue);
}

Even though I don’t quite understand it yet, I think I’m beginning to grasp its outlines and it’s what I’m using now. Thanks to everyone for your help!

Answer 1

OK. So, as you've discovered, your problem is that the default JavaScript sort is not guaranteed to be stable. Specifically, I think that in your mind it works like this: I'll sort by blueness, and then when I sort by greenness the sorter will just move entries in my array up and down but keep them ordered by blueness. Sadly, the universe is not so conveniently arranged; the built-in JS sort is allowed to do the sort how it likes. In particular, it's allowed to just throw the contents of the array into a big bucket and then pull them out sorted by what you asked for, completely ignoring how it was arranged before, and it looks like at least some browsers do precisely that.

There are a couple of ways around this, for your particular example. Firstly, you could still do the sort in three separate calls, but make sure those calls do the sort stably: this would mean that after sorting by blueness, you'd stably sort by greenness and that would give you an array sorted by greenness and in blueness order within that (i.e., precisely what you're looking for). My sorttable library does this by implementing a "shaker sort" or "cocktail sort" method (http://en.wikipedia.org/wiki/Cocktail_sort); essentially, this style of sorting walks through the list a lot and moves items up and down. (In particular, what it does not do is just throw all the list items into a bucket and pull them back out in order.) There's a nice little graphic on the Wikipedia article. This means that "subsorts" stay sorted -- i.e., that the sort is stable, and that will give you what you want.

However, for this use case, I wouldn't worry about doing the sort in three different calls and ensuring that they're stable and all that; instead, I'd do all the sorting in one go. We can think of an rgb colour indicator (255, 192, 80) as actually being a big number in some strange base: to avoid too much math, imagine it's in base 1000 (if that phrase makes no sense, ignore it; just think of this as converting the whole rgb attribute into one number encompassing all of it, a bit like how CSS computes precedences in the cascade). So that number could be thought of as actually 255,192,080. If you compute this number for each of your rows and then sort by this number, it'll all work out, and you'll only have to do the sort once: so instead of doing three sorts, you could do one: sorter.sort(function(a,b) { return (a.red*1000000 + a.green*1000 + a.blue) - (b.red*1000000 + b.green*1000 + b.blue) } and it'll all work out.

Technically, this is slightly inefficient, because you have to compute that "base 1000 number" every time that your sort function is called, which may be (is very likely to be) more than once per row. If that's a big problem (which you can work out by benchmarking it), then you can use a Schwartzian transform (sorry for all the buzzwords here): basically, you work out the base-1000-number for each row once, put them all in a list, sort the list, and then go through the sorted list. So, create a list which looks like [ [255192080, <table row 1>], [255255255, <table row 2>], [192000000, <table row 3>] ], sort that list (with a function like mylist.sort(function(a,b) { return a[0]-b[0]; })), and then walk through that list and appendChild each of the s onto the table, which will sort the whole table in order. You probably don't need this last paragraph for the table you've got, but it may be useful and it certainly doesn't hurt to know about this trick, which sorttable.js also uses.

Answer 2

I would approach this problem in a different manner. It appears you're trying to reconstruct all the data by extracting it from the markup, which can be a perilous task; a more straightforward approach would be to represent all the data you want to render out to the page in a format your programs can understand from the start, and then simply regenerate the markup first on page load and then on each subsequent sort.

For instance:

var colorsData = [
  {
    keyword: 'mediumspringgreen',
    decimalrgb: {
      r: 0,
      g: 250,
      b: 154
    },
    percentrgb: {
      r: 0,
      g: 98,
      b: 60.4
    },
    hsl: {
      h: 157,
      s: 100,
      l: 49
    }
    hex: '00FA9A',
    shorthex: undefined
  },
  {
    //next color...
  }
];

That way, you can run sorts on this array in whatever way you'd like, and you're not trying to rip data out from markup and split it and reassign it and all that.

But really, it seems you're maybe hung up on the sort functions. Running multiple sorts one after the other will get unintended results; you have to run a single sort function that compares the next 'column' in the case the previous one is found to be equal. An RGB sort could look like:

var decimalRgbForwards = function(a,b) {
  var a = a.decimalrgb,
      b = b.decimalrgb;
  if ( a.r === b.r ) {
    if ( a.g === b.g ) {
      return a.b - b.b;
    } else {
      return a.g - b.g;
    }
  } else {
    return a.r - b.r;
  }
};

So two colors with matching r and g values would return for equality on the b value, which is just what you're looking for.

Then, you can apply the sort:

colorsData.sort(decimalRgbForwards);

..and finally iterate through that array to rebuild the markup inside the table.

Hope it helps, sir-