javascript - Sort a list of strings given a predefined order -

javascript - Sort a list of strings given a predefined order -

i have array of colors i'd sort order. however, don't want sort them using "natural" ordering, rather maintain them in order:

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

so, example, sorting array

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

should give back

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

here's have far:

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

i'm not sure how scales - if order has 100 or 1000 elements 'items' has 10?

what good, scalable way accomplish this?

as @shmiddty pointed out in comment, 1 simple way utilize library sort function custom comparator, this:

items.sort(function(a,b) { homecoming order.indexof(a) - order.indexof(b); });

i'd start that. if it's fast enough, great! go it.

from time complexity perspective, let's imagine have list of n elements sort , master ordering has k elements in it. calling sort custom comparator create o(n log n) comparisons, each of takes time o(k) due cost of scanning on list. gives runtime of o(kn log n). assuming k little - is, master list isn't long - fine.

if k big - example, if have fixed ordering of cities in world, or - approach not scale well. in case, may want add together layer of indirection problem creating dictionary straight mapping sorted index. here's 1 way this:

var indexmap = {}; (var = 0; < order.length; i++) { indexmap[order[i]] = i; } items.sort(function(a,b) { homecoming indexmap[a] - indexmap[b]; });

this has time complexity o(k + n log n), big k it's appreciably faster.

javascript sorting time-complexity