Three-way compare function for Arrays in Javascript

Question

There have been other questions about How to compare arrays in JavaScript?. What I want to know is the most straightforward way to write/use a three-way comparison function like the one required by Array.sort(). Here's an example using the default one which doesn't work well:

> [ [4,5,10], [4,5,6], [4,1,2] ].sort() // no compare function, uses the default one
[ [ 4, 1, 2 ],
  [ 4, 5, 10 ], // oops, string sorting makes 10 < 6
  [ 4, 5, 6 ] ]

This is what I came up with:

// return -1 if lhs is "less" than rhs, +1 if "greater", and 0 if equal
// if lhs and rhs have different lengths, only the shorter part will be considered
function compareArrays(lhs, rhs) {
  for (var ii = 0; ii < lhs.length; ii++) {
    if (lhs[ii] < rhs[ii]) {
      return -1;
    } else if (lhs[ii] > rhs[ii]) {
      return 1;
    }
  }
  return 0;
}

Which gives us what we want:

> [ [4,5,10], [4,5,6], [4,1,2] ].sort(compareArrays)
[ [ 4, 1, 2 ],
  [ 4, 5, 6 ],
  [ 4, 5, 10 ] ]

Is there something more like a one-liner, or must I define my own function whenever I want to do this?

Supporting old browsers is not a requirement. Using libraries like jQuery or Underscore is OK.

One way to look at this is "The first nonzero value from a standard three-way compare applied to each pair of elements." But even then I haven't found a good fit in existing libraries.

Maritzamariupol

Isn't your current solution a "one liner"? You could reduce the sort function to an almost one liner using forEach and the conditional operator ?:, but that's just going to reduce the amount of code by a few characters in one place, not make it faster or more reliable. – Taunyataupe

It's not going to get much smaller than your compareArrays() function. – Dowland

"Using libraries like jQuery or Underscore is OK." - Well then, turn your function into a library. There is your one-liner. – Set

Btw, your function does not work for arrays of different length. – Zielsdorf

Answer 1

I'd go with a generic comparison-maker function to be used in a functional way:

function compareArrays(compareItems) {
    return function(a, b) {
        for (var r, i=0, l=Math.min(a.length, b.length); i<l; i++)
            if (0 != (r = compareItems(a[i], b[i])))
                return r;
        return a.length - b.length;
     };
}
// Examples:
var compareNumberArrays = compareArray(function(a,b){ return a-b; }),
    compareGenericArrays = compareArray(function(a,b){ return +(a>b)||-(b>a); });

Now you can use

[ [4,5,10], [4,5,6], [4,1,2], [4,5] ].sort(compareNumberArrays)

Is there something more like a one-liner, or must I define my own function whenever I want to do this?

Comparing arrays is too complex for a one-liner, you should use a helper function. There's no built-in one that you can use everywhere.

Zielsdorf

Answer 2

Probably not the shortest possible, but the fewest lines I can get to sensibly is:

function compareArrays(lhs, rhs) {
  var result;
  lhs.some(function(v, i) {
    return (result = v - rhs[i]);
  });
  return result;
}

or less sensibly:

function compareArrays(lhs, rhs, r) {
  lhs.some(function(v, i) {return (r = v - rhs[i])});
  return r;
}

Edit

Seems you don't want numbers. The compare part can be any relationship you want, e.g. for strings:

function compareArrays(lhs, rhs, r) {
  lhs.some(function(v, i) {return (r = v < rhs[i]? -1 : v > rhs[i]? 1 : 0)});
  return r;
}

[['a','b','c'],['a','c','d'],['a','b','d']].sort(compareArrays) // a,b,c,a,b,d,a,c,d 

But the compare function needs to know what it's getting so it doesn't sort numbers as strings or strings as numbers (and so on…).

Taunyataupe

Thanks--this use of some() is interesting and fits my conceptual formulation of the problem. Now if only there were a standard "three-way compare" function matching the semantics of the one applied by after to-stringing in sort().... – Maritzamariupol

On further consideration, I realize that what I'd really want from some() is more like "Return the first truthy value produced by the callback, or a specified default value if none found." I looked for something like this in Underscore and Lo-dash and came up empty-handed. – Maritzamariupol

This function does not work for arrays of different length. Do you think you can adapt it easily? – Zielsdorf

@JohnZwinck—isn't that what my answer does? some returns the first truthy result or defaults to 0 if none found. – Taunyataupe

@Bergi—yes, provided rules are provided on how to handle them, e.g. include an i in rhs test or similar and a value to return if it returns false. – Taunyataupe

@RobG: that's not what the documentation says nor what my implementation does: some() returns true when the first truthy result is produced by the callback. It does not return the result produced by the callback. – Maritzamariupol

@JohnZwinck—ah yes, I should have said compareArrays returns…. Are you trying to replace the compare function with a single expression using only built–in Array methods? some, reduce and filter all have aspects that are close, but none actually does it. – Taunyataupe

Answer 3

If you know that they are always triplets of numbers (arrays of length 3), you could do this:

function combineNum(array) {
    return (array[0] * 100) + (array[1] * 10) + array[2];
}

function compareArrays(lhs, rhs) {
    return combineNum(rhs) - combineNum(lhs);
}

Dowland

That also assumes the values in the arrays are always numeric, which is not always the case for me. – Maritzamariupol

@JohnZwinck - yes it does assume that. All your examples were numeric so I thought that was the problem you were trying to solve. Oh well, that was my shot at shortening it. So, what is your real objective here? You have a working example of code. There only needs to be one copy of it in your project and you can then just refer to it. Why are you trying to shave a line or two off it? – Dowland

It seemed like something that should be possible without hauling around such a trivial function. I guess I'm accustomed to languages where things like comparing arrays is more built-in...but even then, this felt like something that jQuery or Underscore should be able to do without such tedium. Also, even my working function is not optimal: it wastes time if lhs.length is very different from rhs.length...I could add more code to fix that, but this is basically a waste of time if there's an existing function that could do it. – Maritzamariupol

That's also assuming that they are single digits (or at least of equal magnitude), not any numbers. – Zielsdorf

@Zielsdorf - Yes, if you want to allow much larger numbers, you can spread out the weighting factors as much as you want. Just trying to offer another conceptual idea here that doesn't have to do so many cell by cell comparisons. – Dowland

@JohnZwinck - there's nothing built into JS to do this. Heck JS can't even sort a regular single numeric array properly without a custom sort function. So, you build your own library function to do it, include it in your project and just refer to it whenever you want. Once you have the function, that's really no different than finding one in an existing library and then including that one. Either way you're including a function to do the sort comparison for you. In any project, I'm always finding little common functions that I can use in more than one place. – Dowland