How to sort a 2D array based on the sum of each row?

Question

Excuse me, a quick question:

I have a 2D array of elements where each element has an int value encapsulated. Something like this:

MyComponent = {... , value: 2, ...} // each instance has a value property

MyArray = [
            [Component1, Component2],
            [Component3],
            [Component4, Component5, Component6, Component7],
            ... ]

I would like to sort my 2D array rows, based on the sum of value of elements in each row.

A little detailed: I have groups of choices (combinations) for the user to select, where each single choice in any group has a certain value. I would like to show the combinations that have the highest sum or total first (so it is descending).

What is a quick and efficient way to achieve that in javascript?

MyArray.sort((a, b) => b.reduce((s, o) => s + o.value, 0) - a.reduce((s, o) => s + o.value, 0)); — ibrahim mahrir
– ibrahim mahrir, Commented May 1, 2017 at 16:59
@ibrahimmahrir Excellent ! just a note for readers: the above is ascending and to get it descending you just have to swap the expressions . +1 ! — Khalil Khalaf
– Khalil Khalaf, Commented May 1, 2017 at 17:11
The suggestion given by @ibrahimmahrir is short, but has the disadvantage of performing O(n log(n)) array summations where n is the length of MyArray while only n such summations are necessary. — le_m
– le_m, Commented May 1, 2017 at 17:19

Khalil Khalaf · Accepted Answer · 2017-05-01 17:59:36Z

var originalArray = [
    [{value: 2}, {value: 3}],
    [{value: 11}],
    [{value: 1}, {value: 2}, {value: 3}, {value: 4}]
];
var sortedArray = originalArray.sort(function(row1, row2) {
    add = function(a, b) {return a + b.value};
    return row1.reduce(add, 0) - row2.reduce(add, 0);
});
console.log(sortedArray);

Let's break this down, shall we?

We start with the original array:

var originalArray = [
    [{value: 2}, {value: 3}],
    [{value: 11}],
    [{value: 1}, {value: 2}, {value: 3}, {value: 4}]
];

Then we sort it. Let's work from the inside out. First, how do we calculate the sum of a row? We can use the reduce function:

exampleRow = [{value: 2}, {value: 3}];
add = function(a, b) {return a + b.value};
console.log(exampleRow.reduce(add, 0));

The reduce function takes in another function (add in this case) and uses it to iterate over an array and reduce it to a single item (usually a number). reduce needs a function that takes in two arguments - the running total, and the next item. Reduce roughly does the following:

array.prototype.reduce = function(fn, initial) {
    runningTotal = initial;
    for (var i = 0; i <= array.length; i++) {
        runningTotal = fn(runningTotal, array[i]);
    }
    return runningTotal;
}

In words, it starts with the initial value, and then runs your function over and over, with each run using the last run's output and the next item in the array.

In our case, the fn function is add:

add = function(a, b) {return a + b.value};

add is very simple; it takes the running total (a) and adds the value of the next item (b). Over the entire array, this simplifies to 0 + array[0].value + array[1].value + ... + array[array.length-1].value - the sum of the array.

We're almost there! The last part is the actual sorting. We do this with the sort function (surprise!). The sort function also takes in a function with two arguments that it uses to iterate over the array. The function you give to sort, however, has to return a number. sort uses this function to compare the two arguments; if the output is positive, the first item is 'bigger', while if the output is negative, the second item is 'bigger'. (If the output is zero they are equal.) sort uses this to sort the array in ascending order.

In our case, our function takes in the two rows and returns the sum of the first minus the sum of the other. This means that if the first row's sum is greater ist will be later in the array and vice versa.

Both answers work, this and le_m's, and I will accept this because it is well detailed.

le_m · Accepted Answer · 2017-05-01 17:53:54Z

1

The following sorting function precomputes row-sums to avoid redundant summations and stores the sums in a Map for fast retrieval within the array.sort() callback:

// Sort a 2D array in-place by the sum of its rows:
function sortByRowSum(array) {
  let sums = new Map(array.map(row =>
    [row, row.reduce((sum, element) => sum + element, 0)]
  ));
  return array.sort((a, b) => sums.get(a) - sums.get(b));
}

// Example:
console.log(sortByRowSum([[1, 3], [2], [0, 1, 8], [0]]));

Since your row elements aren't simple numbers as in the example above, you would need to adapt the reduce callback to the structure of your row elements, e.g.:

let sums = new Map(array.map(row =>
  [row, row.reduce((sum, component)=> sum + component.value, 0)]
));

edited May 1, 2017 at 17:53

answered May 1, 2017 at 17:32

le_m

20.4k10 gold badges70 silver badges78 bronze badges

Comments

Aprillion · Accepted Answer · 2017-05-08 11:58:01Z

Comparing performance of 2 solutions for myself, might be useful for others, feel free to optimize more: https://jsperf.com/sort-array-by-sum-of-rows/1

I got only 30-70% improvement in Firefox, Chrome and Edge (my ES6 code does not compile in IE11), so the reduced readability is not worth it IMHO:

const simpleSorter = (arr) => [...arr].sort(
  (a, b) => b.reduce((sum, i) => sum + i.value, 0) -
            a.reduce((sum, i) => sum + i.value, 0)
)

const fasterSorter = (arr) => {
  // note: should use stable sort for equal row scores
  const rowScores = arr.map((row, index) => ({
    score: row.reduce((sum, i, index) => sum + i.value, 0),
    index
  })).sort((a, b) => b.score - a.score)
  return rowScores.map(s => arr[s.index])
}



const rand = () => Math.floor((Math.random() * 10)) + 1
const idGenerator = (() => {
  let i = 0
  return () => i++
})()
const componentGenerator = () => ({a: 'x', value: rand(), id: idGenerator()})
const rowGenerator = () => [...Array(rand())].map(componentGenerator)
const myArray = [...Array(10)].map(rowGenerator)
const prettyPrinter = (arr) => arr.map(i => {
  const temp = i.map(j => j.value)
  return temp.join(' + ') + ' = ' + temp.reduce((a, b) => a + b)
})

const myArraySimpleSorted = simpleSorter(myArray)
const myArrayFasterSorted = fasterSorter(myArray)

console.log('test',
            prettyPrinter(myArraySimpleSorted).toString() ===
            prettyPrinter(myArrayFasterSorted).toString())

console.log('myArray', prettyPrinter(myArray))
console.log('myArraySimpleSorted', prettyPrinter(myArraySimpleSorted))
console.log('myArrayFasterSorted', prettyPrinter(myArrayFasterSorted))
console.log('first in myArray', myArray[0][0])
console.log('first in myArraySimpleSorted', myArraySimpleSorted[0][0])

Collectives™ on Stack Overflow

How to sort a 2D array based on the sum of each row?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related