Ordering lists in Javascript

Question

I have a list whose members are nested lists of integers, for example :

[ [1,2], [], [1,2,3], [ [1,2],3], [1,2,4], [ [], [1,2] ], [34,5,6], [-1,66] ]

I want to sort this list, using (what every other language in the world) would consider standard ordering of nested lists. For example :

[] < [ [1] ] < [ [1,2] ] < [ [2] ] < [ [11] ]

l.sort() messes this up, because it turns the lists into strings

Is there an easy way, either in javascript (or a common library like lodash) to get a proper sort of nested lists?

I'm not seeing lodash `_.sort()` in either version 2, 3 or 4 - which function specifically are you using? — random_user_name, Feb 16 '16 at 19:39
The 11 before 2 is because your array contents are probably strings, not numbers. Use `parseInt` in your comparer or map with parseInt beforehand. — doogle, Feb 16 '16 at 19:48
lodash doesn't have a sort at all, I'm using javascript sort currently. — Chris Jefferson, Feb 16 '16 at 20:00
Have a look at [this](http://stackoverflow.com/a/23883042/1048572). Btw, every other language would gag on inhomogeneously nested lists. It's not even intuitive whether `[1, [2, 3], 4]` would be larger than `[1, [2], 3, 4]` or not. Do you just want to flatten them? — Bergi, Feb 19 '16 at 05:39
Here's an easy option, let's go with what python says (other languages, like GAP, agree) [[], [-1, 66], [1, 2], [1, 2, 3], [1, 2, 4], [34, 5, 6], [[], [1, 2]], [[1, 2], 3]] In general python defines recursively. Go through each element of the array, All integers sort smaller than all arrays. — Chris Jefferson, Apr 22 '17 at 16:11

score 2 · Accepted Answer · answered Apr 22 '17 at 23:37

Here's a system of two mutually recursive functions, the first one compares arrays to non-arrays and numbers to numbers, the second compares arrays elementwise.

function cmp(x, y) {
    let ax = Array.isArray(x),
        ay = Array.isArray(y);
    return ax - ay || (ax ? cmpArr(x, y) : x - y);
}

function cmpArr(x, y) {
    let xlen = x.length,
        ylen = y.length,
        min = xlen < ylen ? xlen : ylen,
        c;

    for (let i = 0; i < min; i++) {
        if (c = cmp(x[i], y[i]))
            return c;
    }

    return xlen - ylen;
}

//

a = [[1, 2], [], [1, 2, 3], [[1, 2], 3], [1, 2, 4], [[], [1, 2]], [34, 5, 6], [-1, 66]];
a.sort(cmp);
console.log(JSON.stringify(a))

Thanks very much for this answer. It's very useful. – Chris Jefferson Apr 24 '17 at 18:07 — Chris Jefferson, Apr 24 '17 at 18:07

phenxd · Answer 2 · 2016-02-16T21:03:33.780

1

EDIT : Okay, inspired by @Damien's answer, this is dirty but will work perfectly. Wish I had managed something cleaner.

You might be able to use lodash's differenceWith to 'compress' the array for each values wich are equals. But jsfiddle doesn't have the latest version of lodash so I can't test it.

var l = [[1,2],[],[1,3],[34, 5, 6],[-1, 66]];

l = l.sort(function(a, b) {

  var minLength = Math.min(a.length, b.length);

  for (var i = 0; i < minLength; i++) { // Compare the "matching pairs"
    if (a[i] < b[i]) {
      return -1;
    } else if(a[i] > b[i]){
        return 1;
    }
  }

  return a.length - b.length; // If all pairs were equals, use list length
});

Fiddle

edited Feb 16 '16 at 21:03

answered Feb 16 '16 at 19:44

phenxd

689
4
17

My bad. Fixed. It now uses the first number of every array. – phenxd Feb 16 '16 at 19:54
My example was too simple -- my lists can have the same first element, for example I could have elements [1,2,3,4] and [1,2,3,5] – Chris Jefferson Feb 16 '16 at 20:01

Mitch Lillie · Answer 3 · 2016-02-16T20:14:20.747

1

You can use _.sortBy as a shortcut.

_.sortBy(arr, function (o) { return o[0] || Infinity } )

Or, if your interior arrays are not yet sorted:

_.sortBy(arr, function (o) { return someMutatedArr[0] || Infinity } )

EDIT:

I found a better way that sorts beyond the first item in the list, but the empty array is still at the end. You could handle this as an edge case separately, annoying, I know.

var arr = [ [11], [1,3], [2], [], [1], [1,2]]
var count = []

// Get an array that is as long as the longest array with [0, 1, 2, etc]
arr.forEach(function (e, i) { 
  if (e.length > (count.length) ) 
    count.push(count.length -1) 
})

_.sortBy(arr, count)

edited Feb 16 '16 at 20:14

answered Feb 16 '16 at 19:46

Mitch Lillie

2,217
18
25

You can't just only consider the first element of the inner arrays, consider for example sorting `[ [1,2,3,5], [1,2,3,4] ]` – Chris Jefferson Feb 16 '16 at 20:02
Slightly improved solution above. Handling the empty array is just not happening for me, but this will pass your case of `[1,2,3,4/5]`. – Mitch Lillie Feb 16 '16 at 20:15

Damien Fayol · Answer 4 · 2016-02-16T19:45:44.320

0

You can use a custom sort function, see this doc.

Example:

var l = [[1,2], [], [34,5,6], [-1,66]];

l = l.sort(function (a, b) {

  if(!a.length) {
      return -1; 
  }

  if(!b.length) {
      return 1; 
  }

  return a[0] - b[0];
});

You probably have to handle more edge cases, but you have the idea here.

edited Feb 16 '16 at 19:45

answered Feb 16 '16 at 19:38

Damien Fayol

958
7
17

stasovlas · Answer 5 · 2016-02-19T06:02:23.277

0

var res = _.chain(items)
    .groupBy(function (item) {
        return _.chain(item).flattenDeep().max().value() || -1;
    })
    .map(function(val, key){
        return {
            key: parseFloat(key),
            val: val
        };
    })
    .orderBy('key')
    .map(function(item){
        return _.sortBy(item.val, 'length');
    })
    .flatten()
    .value();

for

[[], [ [1] ], [ [1,2] ], [ [2] ], [ [11] ]]

result is

[ [], [ [ 1 ] ], [ [ 1, 2 ] ], [ [ 2 ] ], [ [ 11 ] ] ]

edited Feb 19 '16 at 06:02

answered Feb 18 '16 at 11:37

stasovlas

7,136
2
28
29

Have you just struck it lucky here, that the largest and smallest elements in my arrays help you sort? In general I might have the lists [1,2,10] and [1,3,5], and [1,2,10] should come first. Is it non-obvious what ordering I want? – Chris Jefferson Feb 18 '16 at 19:51

Ordering lists in Javascript

5 Answers5