Javascript - Faster, More Efficient Method for Sorting Javascript Object based on Sorted Array of _id?

Question

We have MongoDB docs that look like this:

var JavascriptObject = {
  DbDocs : [
    {
      _id : "1",
      {..more values..}
    },
    {
      _id : "2",
      {..more values..}
    },
    {
      _id : "3",
      {..more values..}
    }
  ]
}

Based on certain values in the JavascriptObject, we order an array of the _id from the documents, and the result is this:

var OrderedArray = [ 2, 1, 3 ];

Right now, we're rebuilding the entire JavascriptObject by matching the _id in the OrderedArray with the _id in DbDocs:

var JavascriptObjectToRebuild = [];
var DbDocuments = JavascriptObject.DbDocs;
var DocumentCount = 0;

for (var OrderedNumber in OrderedArray) {
  for (var Document in DbDocuments) {
    if ( DbDocuments[Document]._id === OrderedArray[OrderedNumber] ) {

      JavascriptObjectToRebuild[DocumentCount] = {}; // new Document Object

      JavascriptObjectToRebuild[DocumentCount]._id = DbDocuments[Document]._id;
      JavascriptObjectToRebuild[DocumentCount]...more values = DbDocuments[Document]...more values;

      DocumentCount++; // increment

    }
  }
}

var SortedJavascriptObject = { DbDocs: [] }; // format for client-side templating

for (var Document in JSONToRebuild) {
  SortedJavascriptObject.DbDocs.push(JavascriptObjectToRebuild[Document]);
}

Is there a faster more efficient way to sort the JavascriptObject based on this OrderedArray?

There is no JSON in this question at all. JSON is a **textual** notation. When you're dealing with objects and arrays in JavaScript, you're dealing with JavaScript objects and arrays. The only time you're dealing with JSON in JavaScript code is when it's inside a **string**. — T.J. Crowder, Aug 07 '15 at 07:05
Is there any reason you can't just call `sort` on `JSON.DbDocs` directly? — T.J. Crowder, Aug 07 '15 at 07:06
I am sorry to say, but simple Array.sort() will do it... Have a look here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort — Akxe, Aug 07 '15 at 07:07
@Akxe figured as much, but all the examples are for ascending and descending.. how do we apply the custom sorting that's captured in OrderedArray? — Stacks, Aug 07 '15 at 07:09
@Maji: What *is* the custom sorting? You can put things in any order you like. The code above just tells us that it should be 2, 1, 3, not how you go that order. — T.J. Crowder, Aug 07 '15 at 07:10
@T.J.Crowder the custom sorting is the OrderedArray of _id .. what do we pass to sort() so that JavascriptObject.DbDocs is sorted based on OrderedArray? — Stacks, Aug 07 '15 at 07:11
@Maji: You're missing the point. How did you get that order? You don't want to get an array with the desired order, you want to **directly** sort your existing array. — T.J. Crowder, Aug 07 '15 at 07:11
@T.J.Crowder not possible.. the order is the result of an algorithm that exports these results, from a completely different language.. — Stacks, Aug 07 '15 at 07:12
@Maji: What does "exporting" an algorithm look like? Are you saying that the logic is not accessible within your code at all?? — T.J. Crowder, Aug 07 '15 at 07:12
@Maji: I've updated my answer to show how to use `OrderedArray` with `sort`, but if you can implement the sorting logic directly rather than indirectly, it might be better. Obviously, that may not be possible or desireable for reasons outside the question... — T.J. Crowder, Aug 07 '15 at 07:15

score 3 · Accepted Answer · edited May 23 '17 at 12:06

See update below if it's impossible to sort directly and you have to use OrderedArray instead.

If you can apply your criteria within the callback of the Array#sort function (e.g., if you can do it by comparing two entries in the array to one another), you can simply sort JSON.DbDocs directly.

Here's an example that sorts based on the numeric value of _id; naturally you'd replace that with your logic comparing objects.

Also note I've changed the name of the top-level variable (JSON is kinda in use, and in any case, it's not JSON):

var Obj = {
  DbDocs : [
    {
      _id : "2",
      more: "two"
    },
    {
      _id : "1",
      more: "one"
    },
    {
      _id : "3",
       more: "three"
    }
  ]
};
Obj.DbDocs.sort(function(a, b) {
  return +a._id - +b._id; // Replace with your logic comparing a and b
});
document.querySelector('pre').innerHTML = JSON.stringify(Obj, null, 2);

<pre></pre>

If it's impossible to sort directly and you have to work from OrderedArray, then it's still possible with sort, but it's less elegant: You use Array#indexOf to find out where each entry in the array should be:

Obj.DbDocs.sort(function(a, b) {
  return OrderedArray.indexOf(+a._id) - OrderedArray.indexOf(+b._id);
});

(The + converts the IDs from strings to numbers, since OrderedArray contains numbers in your question, but the ID values are strings.)

Live Example:

var Obj = {
  DbDocs : [
    {
      _id : "1",
      more: "one"
    },
    {
      _id : "2",
      more: "two"
    },
    {
      _id : "3",
       more: "three"
    }
  ]
};
var OrderedArray = [2, 1, 3];
Obj.DbDocs.sort(function(a, b) {
  return OrderedArray.indexOf(+a._id) - OrderedArray.indexOf(+b._id);
});
document.querySelector('pre').innerHTML = JSON.stringify(Obj, null, 2);

<pre></pre>

If there are going to be lots of entries in OrderedArray, you might want to make a lookup object first, to avoid lots of indexOf calls (which are costly: (georg did that in an answer, but he's since deleted it for some reason)

var OrderMap = {}
OrderedArray.forEach(function(entry, index) {
  OrderMap[entry] = index;
});
Obj.DbDocs.sort(function(a, b) {
  return OrderMap[a._id] - OrderMap[b._id];
});

(We don't need to convert the IDs to numbers because property names are always strings, so we've converted the numbers to strings when building the map.)

Live Example:

var Obj = {
  DbDocs : [
    {
      _id : "1",
      more: "one"
    },
    {
      _id : "2",
      more: "two"
    },
    {
      _id : "3",
       more: "three"
    }
  ]
};
var OrderedArray = [2, 1, 3];
var OrderMap = {}
OrderedArray.forEach(function(entry, index) {
  OrderMap[entry] = index;
});
Obj.DbDocs.sort(function(a, b) {
  return OrderMap[a._id] - OrderMap[b._id];
});
document.querySelector('pre').innerHTML = JSON.stringify(Obj, null, 2);

<pre></pre>

thanks for being thorough.. `Obj.DbDocs.sort(function(a, b) { return OrderedArray.indexOf(+a._id) - OrderedArray.indexOf(+b._id); });` works like a charm — Stacks, Aug 07 '15 at 07:59

score 1 · Answer 2 · edited May 23 '17 at 12:30

1

303 see other

......

Convert OrderedNumber into a hash _id => position:

sorter = {}
OrderedNumber.forEach(function(_id, pos) {
    sorter[_id] = pos
})

and then sort the target array by comparing id's positions:

DbDocuments.sort(function(a, b) {
    return sorter[a._id] - sorter[b._id];
})

edited May 23 '17 at 12:30

Community

1
1

answered Aug 07 '15 at 07:13

georg

211,518
52
313
390

Yeah, if `OrderedArray` is of any decent size, this is likely to make the `sort` more efficient. – T.J. Crowder Aug 07 '15 at 07:17

score 1 · Answer 3 · answered Aug 07 '15 at 07:21

As I understood, you want to get result like so,

[{"_id":"2"}, {"_id":"1"}, {"_id":"3"}]

so you can do it with one forEach and indexOf, like so

var JSONDADA = {
    DbDocs : [{_id : "1",}, {_id : "2"}, {_id : "3"}]
};

var DbDocuments = JSONDADA.DbDocs;
var OrderedArray = [ 2, 1, 3 ];
var result = [];

DbDocuments.forEach(function (el) {
    var position = OrderedArray.indexOf(+el._id);
    
    if (position >= 0) {
        result[position] = el;
    }
});
console.log(JSON.stringify(result));

Javascript - Faster, More Efficient Method for Sorting Javascript Object based on Sorted Array of _id?

3 Answers3