1

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?

Improve this question
6
  • I'm not seeing lodash _.sort() in either version 2, 3 or 4 - which function specifically are you using? Commented Feb 16, 2016 at 19:39
  • 1
    The 11 before 2 is because your array contents are probably strings, not numbers. Use parseInt in your comparer or map with parseInt beforehand. Commented Feb 16, 2016 at 19:48
  • lodash doesn't have a sort at all, I'm using javascript sort currently. Commented Feb 16, 2016 at 20:00
  • Have a look at this. 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? Commented Feb 19, 2016 at 5:39
  • What is expected result? Commented Apr 22, 2017 at 15:50

5 Answers 5

Reset to default
2
+100

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))

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks very much for this answer. It's very useful.
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)
Improve this answer

2 Comments

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] ]
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].
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

Improve this answer

2 Comments

My bad. Fixed. It now uses the first number of every array.
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]
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.

Improve this answer

Comments

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 ] ] ]
Improve this answer

1 Comment

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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.