Sort an array based on data in another array

Question

I have two arrays of objects like below:

items = [{"id":"5","tobuy":"1","name":"pop"},
         {"id":"6","tobuy":"1","name":"fish"},
         {"id":"7","tobuy":"0","name":"soda"}]
pkgs =  [{"item_id":"5","store":"Market","aisle":"3"},
         {"item_id":"6","store":"Market","aisle":"2"},
         {"item_id":"6","store":"Dept","aisle":"8"},
         {"item_id":"7","store":"Market","aisle":"4"}]

I'm trying to sort the items array, but I want to leverage the data in the pkgs array.
The "item_id" field in the pkgs array corresponds to the "id" field in the items array.
For example, I want to sort:

• first by "tobuy" in descending order
• then by "store"
• then by "aisle"
• then by "name"

While item_id and id correspond between the two arrays, there is not a 1 to 1 relationship. There could be 0 or more pkgs that correspond to any given item.

(If I had a database, I would just join the tables, but in JavaScript I just have the two related arrays).

I'm not sure how to build the comparator function and pass in the second array.

Thanks for any help.

Answer 1

Perhaps something like this?

items = items.map(function (item, index) {
    return {
        item: item,
        pkg: pkgs[index] //I assumed associated pkgs were at the same index
    };
}).sort(function (a, b) {
   var pkgA = a.pkg, pkgB = b.pkg, r;

   r = +b.item.tobuy - +a.item.tobuy;

   if (r !== 0) return r;

   r = pkgA.store < pkgB.store? -1 : (pkgA.store === pkgB.store? 0 : 1);

   if (r !== 0) return r;

   r = +pkgA.aisle - +pkgB.aisle;

   if (r !== 0) return r;

   return pkgA.name < pkgB.name? -1 : (pkgA.name === pkgB.name? 0 : 1);

}).map(function (item) {
    return item.item;
});

Instead of merging the data, you could also create a lookup map that allows to quickly retrieve the associated package directly from the sort function.

E.g.

var pkgsMap = pkgs.reduce(function (res, pkg) {
    res[pkg.item_id] = pkg;
    return res;
}, {});

Then in the sort function you can do:

var pkgA = pkgsMap[a.id], pkgB = pkgsMap[b.id];

EDIT:

There is actually another field in the pkgs array called "ppu" which is the price per unit. The lowest ppu is the one that would be used.

You can just build your package map using the following and then use the map in the sort function to retrieve the associated package like described above and implement the sort algorithm.

var pkgsMap = pkgs.sort(function (a, b) {
    //not sure what ppu is so I sort it as a string
    return a.ppu < b.ppu? -1 : Number(a.ppu > b.ppu);
}).reduce(function (res, pkg) {
    if (!(pkg.item_id in res)) res[pkg.item_id] = pkg;
    return res;
}, {});

Answer 2

Make a function that generates a comparator, this looks unwieldy but means you can generate any sort order desired

function generateComparator(dict, index, order) {
    return function (a, b) {
        var i, key, direction,
            ai = a[index], av,
            bi = b[index], bv;
        for (i = 0; i < order.length; ++i) {
            key = order[i].key;
            direction = +!!order[i].reverse || -1;
            if (dict[ai].hasOwnProperty(key)) // if in dict, lookup
                av = dict[ai][key];
            else                              // else look up in item
                av = a[key];
            if (dict[bi].hasOwnProperty(key))
                bv = dict[ai][key];
            else
                bv = b[key];
            // console.log(i, key, av, bv, direction); // debug
            if (av === bv)
                continue;
            if (av < bv)
                return direction;
            return -direction;
        }
        return 0;
    };
}

Convert your Arrays into a dictionary

var dict = (function (arr, index) {
    var o = {}, i;
    for (i = 0; i < arr.length; ++i) {
        o[arr[i][index]] = arr[i];
    }
    return o;
}(pkgs, 'item_id'));

Define your sort choices

var order = [
    {key: 'tobuy', reverse: 1},
    {key: 'store'},
    {key: 'aisle'},
    {key: 'name'}
];

Generate comparator with dictionary

var comparator = generateComparator(dict, 'id', order);

Then sort your first Array

items.sort(comparator);
/* [
    {"id": "6", "tobuy": "1", "name": "fish"},
    {"id": "5", "tobuy": "1", "name": "pop"},
    {"id": "7", "tobuy": "0", "name": "soda"}
] */