Sort Javascript array by a given sequence of numbers

Question

I have a Javascript array of object. Each of them has an integer property type in a range between 1 and 4. Depending on the client, I want to sort the array members by an individual number sequence of this type property. My idea was to define an array with the desired sequence, for example const desiredOrder = [4, 2, 3, 1];. Then my script should sort the array of objects by this list, while keeping the overall order. For example:

var list = [
  {id: 1, type: 2},
  {id: 2, type: 4},
  {id: 3, type: 2},
  {id: 4, type: 1},
  {id: 5, type: 2},
  {id; 6, type: 3}
];

var orderedList = [
  {id: 2, type: 4},
  {id: 1, type: 2},
  {id: 3, type: 2},
  {id: 5, type: 2},
  {id; 6, type: 3},
  {id: 4, type: 1}
];

In my real code, there is no actual id! I've just added that to make clear, that the order should not be changed.

How can I achieve that?

Edit:

Thank you for all your ideas. I've created a JSPerf with all four solutions. It looks like the version with the two nested for loops is the fastest by far. You can test it for yourself:

https://jsperf.com/sort-vs-flatmap/1

`the order should not be changed` What you want is a [stable sorting algorithm](https://stackoverflow.com/a/45422645/1541563). — Patrick Roberts, Sep 16 '19 at 10:05
@joyBlanks I know how to use the `sort` method, but not in such a context, where keeping the overall order is a requirement. — André Reichelt, Sep 16 '19 at 10:55
@PatrickRoberts The solution you've mentioned looks quite complex compared to the answers below. What are the advantages of the linked solution (other than that is adds to the prototype)? — André Reichelt, Sep 16 '19 at 11:02

score 3 · Answer 1 · answered Sep 16 '19 at 10:01

3

You can use flatMap and filter for this.

Keep in mind, that there needs to be every possible type in the desiredOrder array, otherwise some items will be lost.

const desiredOrder = [4, 2, 3, 1];

let list = [
  {id: 1, type: 2},
  {id: 2, type: 4},
  {id: 3, type: 2},
  {id: 4, type: 1},
  {id: 5, type: 2},
  {id: 6, type: 3}
];

// Run through all types in the order array
// => flat map will turn all the array results of the filter method into a list of elements
//       eg: [...filterResultArray1, ...filterResultArray2, ]
let result = desiredOrder.flatMap(type =>
  // Get all elements that match the type as an array 
  list.filter(l => l.type == type)
);

console.log(result)

answered Sep 16 '19 at 10:01

MauriceNino

6,214
1
23
60

Thank you for your idea. How would it compare to Nina Scholz' solution? – André Reichelt Sep 16 '19 at 11:09
@AndréReichelt I don't know about performance. I *do* like my solution more, because I personally think it is more readable, but I guess for that everyone needs to decide himself. I just don't like the sort() function in general, as I find it hard to read. – MauriceNino Sep 16 '19 at 11:10
I see your point. MDN states, that `flatMap` is still an experimental technology without any support in Microsoft Edge yet. I have to consider that. – André Reichelt Sep 16 '19 at 11:16
I've added a JSPerf comparison in my question. – André Reichelt Sep 16 '19 at 11:40

Nina Scholz · Answer 2 · 2019-09-16T12:16:16.960

3

You could sort

by the index of typeOrder, for the over all sorting
by the index of mainOrder, for maintaining the original order by taking the object.

var list = [{ id: 1, type: 2 }, { id: 2, type: 4 }, { id: 3, type: 2 }, { id: 4, type: 1 }, { id: 5, type: 2 }, { id: 6, type: 3 }],
    typeOrder = [4, 2, 3, 1],
    mainOrder = list.slice();

list.sort((a, b) =>
    typeOrder.indexOf(a.type) - typeOrder.indexOf(b.type) ||
    mainOrder.indexOf(a) - mainOrder.indexOf(b)
);

console.log(list);

.as-console-wrapper { max-height: 100% !important; top: 0; }

A slightly differnet approach by using a Map

var list = [{ id: 1, type: 2 }, { id: 2, type: 4 }, { id: 3, type: 2 }, { id: 4, type: 1 }, { id: 5, type: 2 }, { id: 6, type: 3 }],
    typeOrder = [4, 2, 3, 1]
    result = Array
        .from(
            list
                .reduce(
                    (m, o) => m.set(o.type, [...(m.get(o.type) || []), o]),
                    typeOrder.reduce((m, t) => m.set(t, []), new Map)
                )
                .values()
        )
        .flat();

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Sep 16 '19 at 12:16

answered Sep 16 '19 at 10:07

Nina Scholz

376,160
25
347
392

2

@PatrickRoberts, thank you for the hint. now it store the orrder and mainatins the original order. – Nina Scholz Sep 16 '19 at 10:20
Do I understand it correctly, that your solution requires the whole array to be copied once? Is that a problem? – André Reichelt Sep 16 '19 at 11:07
no, it just takes the references to the objects in a new array. it is used for getting the indices, later. – Nina Scholz Sep 16 '19 at 11:08
Ah, I see. It's not that the array contains a lot of elements, but the objects can be rather large. They contain a list of sub entries each. – André Reichelt Sep 16 '19 at 11:13
it does not matter. – Nina Scholz Sep 16 '19 at 11:15
Thank you for your further explanations. I've added a JSPerf comparison in my question. – André Reichelt Sep 16 '19 at 11:40

Fullstack Guy · Answer 3 · 2019-09-16T11:46:10.777

3

Using the index value in the order list, of the type property of the object you can order your sort.

To make a stable sort I have used the index of occurence of the elements in the list so if there is a tie for the sort order of type I will use the original index:

const order = [4, 2, 3, 1];
const list = [
  {id: 1, type: 2},
  {id: 2, type: 4},
  {id: 3, type: 2},
  {id: 4, type: 1},
  {id: 5, type: 2},
  {id: 6, type: 3}
];

//returns a new sorted list
const sortedList = list
      .map((o, idx) => ({idx, ...o}))
      .sort(({type:type1, idx: idx1}, 
             {type:type2, idx: idx2}) => {
             // use the index if there is a tie
           return order.indexOf(type1) - order.indexOf(type2) || idx1 - idx2;
      })
      .map(({idx, ...o}) => o);
console.log(sortedList);

edited Sep 16 '19 at 11:46

answered Sep 16 '19 at 10:08

Fullstack Guy

16,368
3
29
44

Just one little nitpick: your second `map()` can be simplified to `.map(({ idx, ...o }) => o)`. I personally think the `sort()` would just be more readable overall if you didn't use parameter destructuring for it and just did `a.type`, `b.type`, `a.idx`, `b.idx` but that's more opinion, different strokes for different folks, etc. – Patrick Roberts Sep 16 '19 at 10:29
1

@PatrickRoberts That's a wonderful suggestion! Thank you! – Fullstack Guy Sep 16 '19 at 10:33
This one looks pretty bulky compared to some other solutions. Does it have some (hidden) advantages? – André Reichelt Sep 16 '19 at 11:10
@AndréReichelt In my solution I did 2 things, 1. I copied the original array so sorting would not modify your original array that's why u see `[...list]` 2. Since you wanted a stable sort I had to know the index when there would be a tie. To do that I had to use `map` once for adding the index of the object as a property and once for removing the index after the sort is done using it. – Fullstack Guy Sep 16 '19 at 11:19
Thank you for your further explanations. I've added a JSPerf comparison in my question. – André Reichelt Sep 16 '19 at 11:40

score 3 · Accepted Answer · answered Sep 16 '19 at 10:09

3

Using most simple for loop :

let list1 = [4, 2, 3, 1];
let list = [
  { id: 1, type: 2 },
  { id: 2, type: 4 },
  { id: 3, type: 2 },
  { id: 4, type: 1 },
  { id: 5, type: 2 },
  { id: 6, type: 3 }
];
let orderedList = [];
for (let i = 0; i < list1.length; i++) {
  for (let j = 0; j < list.length; j++) {
    if (list1[i] == list[j].type) {
      orderedList.push(list[j]);
    }
  }
}
console.log(orderedList);

answered Sep 16 '19 at 10:09

Saurabh Agrawal

7,581
2
27
51

Thank you! Looks like a lot of looping through the array, though. – André Reichelt Sep 16 '19 at 11:12
I've added a JSPerf comparison in my question. It looks like your solution is by far the most efficient. – André Reichelt Sep 16 '19 at 11:41
1

@AndréReichelt happy to know it worked for you :) – Saurabh Agrawal Sep 17 '19 at 02:22

Sort Javascript array by a given sequence of numbers

4 Answers4