0

Where the data is a meta array in the following format,

[
  [
        "qux doo",
        "adsf",
        "abcd",
        "zzzz",
        "898jwe9"
  ],
  [
        "abcd",
        "xxrwu",
        "urnr",
        "pupupu",
        "sdsdsd"
  ]
]

Will the following two algorithms ever produce a differing result for different input data values?

data.sort(function(a,b){
  return (JSON.stringify(a) < JSON.stringify(b)) - (JSON.stringify(a) > JSON.stringify(b));
});

data.sort(function(a, b) {
    for (var i = 0; i < Math.min(a.length, b.length); i++) {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});
user2958725
  • 1,355
  • 3
  • 12
  • 16

1 Answers1

1

JSON.stringify() will escape some characters (like double quote characters, backslash character or any control character) so those characters aren't likely to sort properly.

Also, since a space has a lower ascii code than a double quote, if your two arrays start with "abcd " and "abcd", they won't sort properly in the JSON. "abcd " should come after "abcd", but the space has a lower ascii value than the double quote so it will sort before. The same would be true for an exclamation point at the end of the value.

If, according to your comments you also want this to work for non-array members like numbers, a string comparison does not work for comparing two numbers with differing number of digits as 1000 is not less than 2, but "1000" is less than "2".

Also, I would suggest that you use .localeCompare() for comparing two strings in your second algorithm as it already has the built-in positive, negative or zero result.

If all your values are strings or they sort properly via .toString(), you could use .localeCompare() like this:

data.sort(function(a, b) {
    var comp, i;
    for (i = 0; i < Math.min(a.length, b.length); i++) {
        if ((comp = a[i].localeCompare(b[i])) !== 0) return comp;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});

.localeCompare also has options you can use for case sensitivity, for ignoring punctuation, for how to treat accented characters, and a few others.

Per your comment and per MDN, you can get better performance in the comparison with a Collator object (only available in some browsers). Per the doc (I've only tried this code once myself), it works like this:

var collater = new Intl.Collator();
data.sort(function(a, b) {
    var comp, i;
    for (i = 0; i < Math.min(a.length, b.length); i++) {
        if ((comp = collater.compare(a[i], b[i])) !== 0) return comp;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});

Presumably there must be some initialization or overhead that can be done just once this way. Perhaps they build direct lookup sort tables.

But browser support for the Collator object is sparse (IE 11, Chrome, no Firefox, no Safari) so unless you were using this in a browser add-on so the code was specific to only one browser, you'd have to branch on whether it was supported or not and have two implementations.

P.S. If you have any sizable number of outer array elements, thus calling the sort callback a lot of times, it would perform pretty horribly. You could at least make it so that it only does two JSON.stringify() calls each time rather than four.

jfriend00
  • 683,504
  • 96
  • 985
  • 979
  • could you show me how you would integrate `.localeCompare()`? – user2958725 Nov 15 '13 at 03:01
  • @user2958725 - `.localeCompare()` option added to the answer. – jfriend00 Nov 15 '13 at 03:11
  • Oh, I was just referring to having `data` be a flat array, of, say, strings, as opposed to a meta array of arrays, not having number values as the narrowest comparison atom. When you say, "if all your values are strings," you do mean all of the values of each inner-array, correct? Do you know anything about Intl.Collator? According to the [MDN doc for `.localeCompare()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare#Performance), – user2958725 Nov 15 '13 at 04:15
  • "When comparing large numbers of strings, such as in sorting large arrays, it is better to create an Intl.Collator object and use the function provided by its compare property." Do you know anything about that Object? I am indeed sorting very large arrays of 100K+ values, on not-that-great hardware. I looked up the docs, but it seemed really confusing to me. What you posted was really perfect, so if you have a second, would you mind showing me what the equivalent would be using `Intl.Collater`? I want to thank you for the super helpful and informative advice you've given, so thanks! – user2958725 Nov 15 '13 at 04:17
  • I've never heard of the Collater before. I just followed the link to the [MDN doc](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects%2FCollator) and implemented it the way they show which I added to my answer. The catch is that it's not supported in very many browsers (no Firefox, no Safari, only IE 11). It does seem to work in Chrome: http://jsfiddle.net/jfriend00/Ymc9h/ – jfriend00 Nov 15 '13 at 04:30
  • You wanna take a look at my attempt and some other thoughts on it? I didn't notice this until I submitted that post. http://stackoverflow.com/q/19993639/2958725 – user2958725 Nov 15 '13 at 04:39
  • @user2958725 - email sent. – jfriend00 Nov 15 '13 at 05:29
  • Have you seen the email I sent? – user2958725 Nov 15 '13 at 07:12
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/41303/discussion-between-jfriend00-and-user2958725) – jfriend00 Nov 16 '13 at 05:26