Sort a list of strings given a predefined order

Question

I have an array of colors that I'd like to sort into order. However, I don't want to sort them using their "natural" ordering, but rather to keep them in this order:

var order = ['white', 'yellow', 'violet', 'blue', 'orange', 'red', 'maroon', 'brown', 'black'];

So, for example, sorting this array

var items = ['blue', 'violet', 'white', 'black', 'orange'];

should give back

['white', 'violet', 'blue', 'orange', 'black'];

Here's what I have so far:

var itemsInOrder = [];

for (var i=0; i<order.length; i++) {
    if (items.indexOf(order[i]) > -1) {
        itemsInOrder.push(order[i]);
    }
}

I'm not sure how well it scales - what if order has 100 or 1000 elements but 'items' has 10?

What is a good, scalable way to accomplish this?

Answer 1

As @Shmiddty pointed out in a comment, one simple way to do this is to use the library sort function with a custom comparator, like this:

items.sort(function(a,b) {
   return order.indexOf(a) - order.indexOf(b);
});

I'd start with that. If it's fast enough, great! Go with it.

From a time complexity perspective, let's imagine that you have a list of n elements to sort and the master ordering has k elements in it. Then calling sort with a custom comparator will make O(n log n) comparisons, each of which takes time O(k) due to the cost of scanning over the list. That gives a runtime of O(kn log n). Assuming k is small - that is, your master list isn't too long - this is perfectly fine.

If k is large - for example, if you have a fixed ordering of all cities in the world, or something like that - then this approach is not likely to scale well. In that case, you may want to add another layer of indirection to the problem by creating a dictionary directly mapping everything to be sorted to its index. Here's one way to do this:

var indexMap = {};
for (var i = 0; i < order.length; i++) {
    indexMap[order[i]] = i;
}

items.sort(function(a,b) {
   return indexMap[a] - indexMap[b];
});

This has time complexity O(k + n log n), so for very large k it's likely to be appreciably faster.