3

Given an array of objects and a list of values, I want to effectively sort the object so that values of a unique property (say key) follows the order of values in the list.

So for an array:

const users = [
  { key: 'A', name: 'Alice' },
  { key: 'B', name: 'Bob' },
  { key: 'C', name: 'Charlie' },
]

I'd like the function to behave like this:

sortByList(['A', 'B', 'C'], users)
// -> Objects for Alice, Bob, Charlie

sortByList(['C', 'B', 'A'], users)
// -> Objects for Charlie, Bob, Alice

sortByList(['A', 'C', 'B'], users)
// -> Objects for Alice, Charlie, Bob

I came up with an implementation that uses Array::sort on the array and then inside Array::indexOf on the list.

const users = [
  { key: 'A', name: 'Alice' },
  { key: 'B', name: 'Bob' },
  { key: 'C', name: 'Charlie' },
]

const sortByList = (list, arr) => arr.sort(
  (a, b) => list.indexOf(a.key) - list.indexOf(b.key)
);

sortByList(['C', 'B', 'A'], users)

console.log(users)

But I feel this is not an effective solution. The time complexity is O(N^2*log(N)) which is rather high. Is there a better one?

I do not care about in-place sorting or stability, imagine the array has tens to hundreds of items.

Improve this question
4
  • 3
    Looks fine to me and works. If you want it improved, it is more a question for codereview Commented Feb 1, 2021 at 13:56
  • "But I feel this is not an effective solution." - Does it work? Is it not the bottle neck in your app (only objective results from a profiler matter)? If the answer is "yes" for both then why change it? Commented Feb 1, 2021 at 13:56
  • You can use Schwartzian transform to sort this array. const sortByList = (list, arr) => arr .map(o => [list.indexOf(o.key), o]) .sort(([a], [b]) => a - b) .map(([,o]) => o); Commented Feb 1, 2021 at 14:02
  • The answers showed that the original solution was awfully slow even for low number of items. I think this question should not be closed. Commented Feb 1, 2021 at 21:18

4 Answers 4

Reset to default
5

With the limitation, that you can guarantee the keys-list is definitely equal to keys from the users data, you can avoid any sorting and create a temporary map, to generate a new "sorted" array:

const users = [
  { key: 'A', name: 'Alice' },
  { key: 'B', name: 'Bob' },
  { key: 'C', name: 'Charlie' }
]

const orderList = ['A','B','C']

const sortByList = (list, arr) => {
   const tmpMap = arr.reduce((acc, item) => {
      acc[item.key] = item
      return acc
   }, {});

   return list.map((key) => tmpMap[key])
}

console.log(
  sortByList(orderList, users)
)

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This is actually the same as Nina's solution, isn't it?
eol, nope, since Nina's solution is still using actual sorting, when mine is basically array iteration and mapping. O(N*log(N)) vs O(N)
This is the optimum solution, speed-wise! I played around with it building upon Antoine Clausse's perf test: jsbench.me/wnkkmr7d26/1
@RobinPokorny this and Nina's solution are not the same. This assumes that there are no objects with the same key in the array. If there are more than one key: 'A' object, this solution will not work
@adiga, in the question I say that the key is supposed to be unique. And the speed difference is actually mind-blowing.
3

You could take an object with the wanted order for the keys.

By using an object you have an access complexity of O(1) vs O(n) by taking indexOf.

const
    users = [{ key: 'A', name: 'Alice' }, { key: 'B', name: 'Bob' }, { key: 'C', name: 'Charlie' }],
    sortByList = (list, arr) => {
        const order = Object.fromEntries(list.map((k, i) => [k, i]));
        return arr.sort((a, b) => order[a.key] - order[b.key]);
    };

console.log(sortByList(['A', 'B', 'C'], users)); // Alice, Bob, Charlie
console.log(sortByList(['C', 'B', 'A'], users)); // Charlie, Bob, Alice
console.log(sortByList(['A', 'C', 'B'], users)); // Alice, Charlie, Bob
.as-console-wrapper { max-height: 100% !important; top: 0; }

Improve this answer

9 Comments

And this is better because of...?
And the O(2n) because of Object.fromEntries() and list.map()?
O(2n) is O(n), a linear complexity.
I knew that the objection would come... - Yet your solution (to a non-existing problem) adds O(n)
Oh, cool. So this is kind of caching the index for a key, right?
|
0

Pretty sure it's not more efficient. Also, it's prone to error if list contains values with no corresponding key or if arr contains an object with no corresponding key in list but that's the first alternative that comes to my mind:

const sortByList = (list, arr) => {
  const sortedList = [];
  for (let i = 0; i < arr.length; i++) {
    sortedList[arr.findIndex((item) => item.key === list[i])] = arr[i];
  }
  return sortedList;
}
Improve this answer

3 Comments

"it's not more efficient. Also, it's prone to error..." - Then why add it as answer? o.O
Interesting, I could just do list.map(key => arr.find((item) => item.key === key)). That could be faster and it feels straight-forward.
He was asking for other solutions and my solution possibly inspired him. Also, only because I'm sure it's not more efficient than his solution that doesn't necessarily mean I'm right.
0

how about this?

const sortByKeyAndList = (key, list, objects) => objects.sort((a, b) =>
list.findIndex(i => i === a[key]) - list.findIndex(i => i === b[key]))
Improve this answer

1 Comment

This seems to be the same solution, but the key is run-time changeable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.