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 acplish this?
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 acplish this?
Share Improve this question edited Aug 27, 2015 at 20:17 templatetypedef 373k111 gold badges942 silver badges1.1k bronze badges asked Jun 17, 2014 at 22:44 BaltoStarBaltoStar 8,99719 gold badges65 silver badges105 bronze badges 4-
6
items.sort(function(a,b){return order.indexOf(a)-order.indexOf(b);}– Shmiddty Commented Jun 17, 2014 at 22:49 -
var itemsInOrder = items.slice().sort(...)if you don't want to mutate items – Shmiddty Commented Jun 17, 2014 at 22:51 -
@Shmiddty could you explain more how
items.sort()mutatesitems? – BaltoStar Commented Jun 18, 2014 at 18:48 -
Array.prototype.sortwill update the indices of the array being sorted instead of creating and returning a new (sorted) array. – Shmiddty Commented Jun 19, 2014 at 17:56
3 Answers
Reset to default 12As @Shmiddty pointed out in a ment, one simple way to do this is to use the library sort function with a custom parator, 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 plexity 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 parator will make O(n log n) parisons, 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 plexity O(k + n log n), so for very large k it's likely to be appreciably faster.
One thing in addition to the answer by templatetypedef is that if your predefined is "partial" e.g. some items in the list cannot be sorted by your predefined order, then you could separate these out of your list and then concatenate them back at the end of the list afterwards e.g.
var items = [3, 2, 3, 2, 1, 4, 5, 1, 2, 3]
var order = [1, 2, 3]
var unordered = items.filter(t => order.indexOf(t) === -1);
var ordered = items.filter(t => order.indexOf(t) !== -1);
ordered.sort(function(a,b) {
return order.indexOf(a) - order.indexOf(b);
});
var final = ordered.concat(unordered)
console.log(final)
// [ 1, 1, 2, 2, 2, 3, 3, 3, 4, 5 ]
If you don't take this step, then the sort will actually put the unordered items at the front of the list and I didn't have any idea how to change it to move them back to the end without filtering them out first.
If somebody is looking for a simpler code than Colin D to sort the array and add unknown items at the end, here's another example:
let list = ["A", "F", "Banana", "rules", "L", "Juice", "Z"]
let order = ["Banana", "Juice", "rules"]
list.sort((a, b) => {
if (order.indexOf(a) === -1) return 1
if (order.indexOf(b) === -1) return -1
return order.indexOf(a) - order.indexOf(b)
})
console.log(list)
This will log: ["Banana", "Juice", "rules", "A", "F", "L", "Z"]