Sorting an array in Javascript based on predefined order

Question

I have an array:

var homes = [{
    "h_id": "3",
    "city": "Dallas",
    "state": "TX",
    "zip": "75201",
    "price": "162500"
}, {
    "h_id": "4",
    "city": "Bevery Hills",
    "state": "CA",
    "zip": "90210",
    "price": "319250"
}, {
    "h_id": "5",
    "city": "New York",
    "state": "NY",
    "zip": "00010",
    "price": "962500"
}];

And would like to sort it based on the following order

cities = ['New York', 'Dallas', 'Bevery Hills']

What's the best way to achieve it?

Answer 1

There is a standard method Array.prototype.sort() available.

Notice that the sort method does sorting in place, so internals of homes are going to change.

homes.sort(function (a,b){
  return cities.indexOf(a.city) - cities.indexOf(b.city)
});

If you need to keep the initial array unchanged, just make a shallow copy (homes.slice(0)) of it and sort the copy:

const sortedHomes = homes.slice(0).sort(function (a,b){
  return cities.indexOf(a.city) - cities.indexOf(b.city)
});

Answer 2

Since you can use indexOf on cities to look up the final index of any home object, you can do it more efficiently than Array.prototype.sort:

var sortedHomes = new Array(cities.length);

homes.forEach(function (home) {
    var sortedIndex = cities.indexOf(home.city);
    sortedHomes[sortedIndex] = home;
});

^{(This is still O(nm) city name comparisons, time proportional to the product of the number of cities and the number of homes – an improvement over O(nm log n), but still potentially not good with a large number of cities. You can make it O(n) by flipping cities into a hashmap.)}

If multiple homes can share the same city and cities doesn’t contain duplicate entries (seems the most likely situation if this is the case), you can group the homes by city and combine the result as specified by cities:

var homesByCity = {};

homes.forEach(function (home) {
    var cityHomes = homesByCity[home.city];

    if (cityHomes) {
        cityHomes.push(home);
    } else {
        cityHomes = homesByCity[home.city] = [home];
    }
});

var sortedHomes = [];

cities.forEach(function (city) {
    (homesByCity[city] || []).forEach(sortedHomes.push, sortedHomes);
});

^{(The approach is O(n) on the number of cities.)}