Sorting an array by order according to another array

Question

I have an object that is returned from the database as follows: [{id:1},{id:2},{id:3}] . I have another array that sets the order in which the first array should be sorted, for example: [2,3,1] .

I am looking for a method or algorithm that can take these two arrays and return [{id:2},{id:3},{id:1}] . Ideally, this should be sort of efficient, not square.

Answer 1

If you want linear time, first create a hash table from the first array and then select the elements in order, looping the second:

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

Answer 2

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

Answer 3

In your example, the objects are first sorted using id , which makes the task pretty simple. But if that is not the case at all, you can sort the objects by linear time according to your array of id values.

The idea is to first create an index that maps each id value to its position, and then insert each object at the desired position by looking at its id value in the index. This requires iteration over two arrays of length n , which leads to a total execution time of O(n) or linear time. There is no asymptotically faster operation, because it takes linear time 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 />'); } 

Answer 4

As far as I understand, sorting is not needed; at least in your example, the desired resultant 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 result, Input is your first array and an Order array containing the desired positions.

Answer 5

 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]) }; 

Answer 6

Why not just create a new array and push the value from the second array? Correct me if I am wrong

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