CODEWITHSUNDEEP
javascriptarrayssorting
Madao
Madao

Reputation: 77

Javascript: sort multiple arrays with two possible items

I have an array containing a bunch of arrays, where every one of these arrays has the same length and just two possible entries (+1 and -1 or +1 and 0). Now I'm searching for an efficient way to sort these arrays, so if I want to check if the list contains a given array, there is no need to compare the given array with every one in the list.

The list may look like this:

list = [
  [1, 1, -1, 1],
  [-1, 1, -1, 1],
  [1, -1, -1, 1]
];

To be more precise, this list is created in a while loop, where the condition is that the new array created in the loop does not appear in the list yet. Therefore, it would be nice to sort the array on the fly, e.g. insert it at an appropriate place in the list.

To avoid misunderstandings, the loop now looks like this

var list = [];
var array = someArray;
while (indexOfArray(list, array) === -1) {
  list.push(array);
  array = calculateNewArray(array);
}

where indexOfArray is a function that returns the index of the array in list if existing, -1 otherwise, and calculateArray takes the previous array and returns a new one. The problem is that the list may get very long (thousands or tens of thousands of different arrays, which may have a length of several hundred entries), so always compare the new array with every saved array in the list becomes extremely time consuming.

What is an efficient and sound approach to tackle this problem?

Edit: to provide an example, the list above could be sorted as

sortedList = sortList(list)
// sortedList should look like this
[
  [1, 1, -1, 1],
  [1, -1, -1, 1]
  [-1, 1, -1, 1],
]

where first comes the array containing as many +1 in a row as possible, second the one with least fewer +1 and so and, while the last array contains as many -1 as possible in a row.

Upvotes: 1

Views: 73

Answers (2)

Nina Scholz
Nina Scholz

Reputation: 386604

You could use Sorting with map and simply add all values of the inner array.

// the array to be sorted
var list = [[1, 1, -1, 1], [-1, 1, -1, 1], [1, -1, -1, 1]];

// temporary array holds objects with position and sort-value
var mapped = list.map(function (el, i) {
    return { index: i, value: el.reduce(function (a, b) { return a + b; }, 0) };
});

// sorting the mapped array containing the reduced values
mapped.sort(function (a, b) {
    return b.value - a.value;
});

// container for the resulting order
var result = mapped.map(function (el) {
    return list[el.index];
});

console.log(result);

Edit for in situ sorting

Basically, you have two options

  1. use a property for it. (the property sum remains until it became deleted)

var list = [[1, 1, -1, 1], [-1, 1, -1, 1], [1, -1, -1, 1]];

list.forEach(function (el) {
    el.sum = el.reduce(function (a, b) { return a + b; }, 0);
});

list.sort(function (a, b) {
    return b.sum - a.sum;
});

console.log(list);

  1. get for every sort loop the sums (does not need a property, but the perfomance is bad)

function sum(a, b) { return a + b; }

var list = [[1, 1, -1, 1], [-1, 1, -1, 1], [1, -1, -1, 1]];

list.sort(function (a, b) {        
    return b.reduce(sum, 0) - a.reduce(sum, 0);
});

console.log(list);

Upvotes: 1

nicael
nicael

Reputation: 18995

You could just map through the list and sort all the inner arrays with sort().

list = [
  [1, 1, -1, 1],
  [-1, 1, -1, 1],
  [1, -1, -1, 1]
];

list = list.map(function(x){return x.sort(function(a,b){return a-b})});

console.log(list);

It could be even shorter with Javascript ES6:

list = list.map(x=>x.sort((a,b)=>(a-b)));

Upvotes: 0

Related Questions