CODEWITHSUNDEEP
javascriptalgorithmsorting
Alexis
Alexis

Reputation: 25233

Sort array by order according to another array

I have an object that is being returned from a database like this: [{id:1},{id:2},{id:3}]. I have another array which specified the order the first array should be sorted in, like this: [2,3,1].

I'm looking for a method or algorithm that can take in these two arrays and return [{id:2},{id:3},{id:1}]. Ideally it should be sort of efficient and not n squared.

Upvotes: 6

Views: 221

Answers (6)

Michael Laszlo
Michael Laszlo

Reputation: 12239

In your example, the objects are initially sorted by id, which makes the task pretty easy. But if this is not true in general, you can still sort the objects in linear time according to your array of id values.

The idea is to first make an index that maps each id value to its position, and then to insert each object in the desired position by looking up its id value in the index. This requires iterating over two arrays of length n, resulting in an overall runtime of O(n), or linear time. There is no asymptotically faster runtime because it takes linear time just to read the input array.

function objectsSortedBy(objects, keyName, sortedKeys) {
  var n = objects.length,
      index = new Array(n);
  for (var i = 0; i < n; ++i) {  // Get the position of each sorted key.
    index[sortedKeys[i]] = i;
  }
  var sorted = new Array(n);
  for (var i = 0; i < n; ++i) {  // Look up each object key in the index.
    sorted[index[objects[i][keyName]]] = objects[i];
  }
  return sorted;
}

var objects = [{id: 'Tweety', animal: 'bird'},
               {id: 'Mickey', animal: 'mouse'},
               {id: 'Sylvester', animal: 'cat'}],
    sortedIds = ['Tweety', 'Mickey', 'Sylvester'];

var sortedObjects = objectsSortedBy(objects, 'id', sortedIds);

// Check the result.
for (var i = 0; i < sortedObjects.length; ++i) {
  document.write('id: '+sortedObjects[i].id+', animal: '+sortedObjects[i].animal+'<br />');
}

Upvotes: 1

georg
georg

Reputation: 215049

If you want linear time, first build a hashtable from the first array and then pick items in order by looping the second one:

data = [{id:5},{id:2},{id:9}]
order = [9,5,2]

hash = {}
data.forEach(function(x) { hash[x.id] = x })

sorted = order.map(function(x) { return hash[x] })

document.write(JSON.stringify(sorted))

Upvotes: 7

yk1007
yk1007

Reputation: 151

Why not just create new array and push the value from second array in?? Correct me if i wrong

array1 = [];
array2 = [2,3,1];

for ( var i = 0; i < array2 .length; i++ )
{
    array1.push({
         id : array2[i]
     })
}

Upvotes: 0

Chirag Bhatia - chirag64
Chirag Bhatia - chirag64

Reputation: 4526

var objArray = [{id:1},{id:2},{id:3}];
var sortOrder = [2,3,1];

var newObjArray = [];
for (i in sortOrder) {
    newObjArray.push(objArray[(sortOrder[i]) - 1])
};

Upvotes: 0

Barmar
Barmar

Reputation: 782653

    function sortArrayByOrderArray(arr, orderArray) {
        return arr.sort(function(e1, e2) {
            return orderArray.indexOf(e1.id) - orderArray.indexOf(e2.id);
        });
    }

    console.log(sortArrayByOrderArray([{id:1},{id:2},{id:3}], [2,3,1]));

Upvotes: 3

Codor
Codor

Reputation: 17605

To my understanding, sorting is not necessary; at least in your example, the desired resulting array can be generated in linear time as follows.

var Result;
for ( var i = 0; i < Input.length; i++ )
{
    Result[i] = Input[Order[i]-1];
}

Here Result is the desired output, Input is your first array and Order the array containing the desired positions.

Upvotes: 0

Related Questions