How to reduce unsorted array against another sorted array, keeping sorted order?

Question

Given an array of objects named allItems which is pre-sorted, but cannot be sorted again from the information it contains - what is an alternative implementation to the reduce function below that will retain the sorted order of allItems?

The logic below will output:

[{ id: 'd' }, { id: 'a' }, { id: 'b' }]

The desired output is:

[{ id: 'a' }, { id: 'b' }, { id: 'd' }]

// NOTE: allItems is pre-sorted, but lacks the information to re-sort it
const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

// QUESTION: How to create the same output, but in the order they appear in allItems
const unsortedIncludedItems = includedIds.reduce((accumulator, id) => {
  const found = allItems.find(n => n.id === id);
  if (found) accumulator.push(found);
  return accumulator;
}, [])

As mentioned in response to @Ben, simply reversing the logic is a deal breaker for performance reasons.

Answer 1

The issue you have here is that your code reverses the list. You can simply push to the front of the list instead, and the original order will be maintained.

Unfortunately, pushing to the front of a list is slower, it's O(n) rather than O(1). It looks like Array.prototype.unshift is supposed to be faster, but it's still O(n) according to this blog. Assuming that the number of found elements is small you won't notice any performance issues. In that case, replace push with unshift like so:

// NOTE: allItems is pre-sorted, but lacks the information to re-sort it
const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

// QUESTION: How to create the same output, but in the order they appear in allItems
const unsortedIncludedItems = includedIds.reduce((accumulator, id) => {
  const found = allItems.find(n => n.id === id);
  if (found) accumulator.unshift(found);
  return accumulator;
}, [])

Otherwise, these are your options:

1. Create a wrapper around this object that reverses the indexes rather than the array. This can be done with a function like this:

   const getFromEnd = (arr, i) => arr[arr.length - 1 - i]

Note that this can be replaced with arr.at(-i) in new browser versions (last few months). This could be encapsulated within a class if you're feeling OOP inclined.

2. Remember to manually invert the indices wherever you use this array (this will be bug-prone, as you may forget to invert them)
3. Reverse the array. As shown in this fiddle, even with 10,000 elements, the performance is not bad. Assuming this isn't a hotpath or user-interactive code, I think that even 100,000 is probably fine.

Answer 2

Update

Example B will use the index of the input array to sort the filtered array.

Try .filter() and .include() to get the desired objects and then .sort() by each object's string value. See Example A.

Another way is to use .flatMap() and .include() to get an array of arrays.

// each index is from the original array
[ [15, {id: 'x'}], [0, {id: 'z'}], [8, {id: 'y'}] ]

Then use .sort() on each sub-array index.

[ [0, {id: 'z'}], [8, {id: 'y'}], [15, {id: 'x'}] ] 

Finally, use .flatMap() once more to extract the objects and flatten the array of arrays into an array of objects.

 [ {id: 'z'},  {id: 'y'},  {id: 'x'} ]

See Example B

Example A (sort by value)

const all = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const values = ['d', 'a', 'b'];

const sortByStringValue = (array, vArray, key) => array.filter(obj => vArray.includes(obj[key])).sort((a, b) => a[key].localeCompare(b[key]));

console.log(JSON.stringify(sortByStringValue(all, values, 'id')));

---

Example B (sort by index)

const all = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];
const values = ['d', 'a', 'b'];

const alt = [{name:'Matt'}, {name:'Joe'}, {name:'Jane'}, {name:'Lynda'}, {name:'Shelly'}, {name:'Alice'}];
const filter = ['Shelly', 'Matt', 'Lynda'];

const sortByIndex = (array, vArray, key) => array.flatMap((obj, idx) => vArray.includes(obj[key]) ? [[idx, obj]] : []).sort((a, b) => a[0] - b[0]).flatMap(sub => [sub[1]]);

console.log(JSON.stringify(sortByIndex(all, values, 'id')));
   
console.log(JSON.stringify(sortByIndex(alt, filter, 'name')));

Answer 3

Instead of iterating over the includedIds (in the wrong order) and seeing whether you can find them in allItems, just iterate over allItems (which is the right order) and see whether you can find their ids in includedIds:

const allItems = [{id:'a'}, {id:'b'}, {id:'c'}, {id:'d'}, {id:'e'}, {id:'f'}];

const includedIds = ['d', 'a', 'b'];

const includedItems = allItems.filter(item => includedIds.includes(item.id));

Answer 4

Why not just reverse the logic, Filter out the ids which not suppose to be includes.

// NOTE: allItems is pre-sorted, but lacks the information to re-sort it
const allItems = [
  { id: "a" },
  { id: "b" },
  { id: "c" },
  { id: "d" },
  { id: "e" },
  { id: "f" },
];

const includedIds = ["d", "a", "b"];

const findElms = (items, includedIds) => items.filter((n) => includedIds.includes(n.id))

console.log(findElms(allItems, includedIds));