Sorting array of objects by property to match a provided list

user_1517783 0
Viewed 237

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.

sorting arrays javascript
4 Answers

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

user_21205410

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

user_14476750

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;
}
user_7053770

how about this?

const sortByKeyAndList = (key, list, objects) => objects.sort((a, b) =>
list.findIndex(i => i === a[key]) - list.findIndex(i => i === b[key]))
user_74396720
Related