javascript - Sort an array of objects by property based on another array of reference IDs -

i have array of objects similar this:

[   {     ref: "ctb98",     name: "joe"         },   {     ref: "htf76",     name: "alice"         },   {     ref: "jhu90",     name: "tom"         },   {     ref: "adf56",     name: "mary"         } ] 

and in array have exact order meant in, referenced ref property:

["jhu90", "htf76", "ctb98", "adf56"]   

i'd rearrange order of first array of objects, ref values on each object follow same order values in reference array above.

i'm new computer science, select answer best explanation of technique.

i think want create hash of objects indexed ref prevent o(n^2) time.

this method let reorder in o(n) time @ cost of o(n) space.

var arr = [{    ref: "ctb98",    name: "joe"  }, {    ref: "htf76",    name: "alice"  }, {    ref: "jhu90",    name: "tom"  }, {    ref: "adf56",    name: "mary"  }];  var order = ["jhu90", "htf76", "ctb98", "adf56"];  var result = reorder(arr, order);    function reorder(arr, order) {    var hash = object.create(null);    arr.foreach(function(obj) {      hash[obj.ref] = obj;    });    return order.map(function(refkey) {      return hash[refkey];    });  }    document.getelementbyid("result").innerhtml = json.stringify(result, null, 2);

<pre id="result"></pre>

time complexity

using various methods involve indexof or nested loops / .foreach cause amount of time required increase in quadratic fashion o(n^2). each of n element may need perform n operations.

creating hash object uses each object's ref property key object allows looking object ref constant time operation, o(1). creation of hash done in linear time, o(n), because insertion hash object o(1) performed n times.

after hash made, perform o(n) operation iterating "order" array of n items, doing o(1) lookup each order key final array.

so overall time complexity of method o(2n) still o(n).

this simplified explanation, not taking account hash table insertion amortized^{[1] [2]} o(1).

---

benchmarks

function polynomialsort(objs, order) {    var arr = [];    order.foreach(function(key) {      objs.foreach(function(o) {        if (o.ref === key) {          arr.push(o);        }      });    });    return arr;  }    function linearsort(objs, order) {    var hash = object.create(null);    objs.foreach(function(el) {      hash[el.ref] = el;    });      return order.map(function(el) {      return hash[el];    });  }    var lessobjs = [];  var lessorder = [];    (var = 1; < 100; i++) {    lessobjs.push({ref:i});    lessorder.push(i);  }  shuffle(lessorder);    console.log(100, "items:");  timer(polynomialsort, lessobjs, lessorder);  timer(linearsort, lessobjs, lessorder);    var moreobjs = [];  var moreorder = [];    (var = 1; < 10000; i++) {    moreobjs.push({ref:i});    moreorder.push(i);  }  shuffle(moreorder);    console.log(10000, "items:");  timer(polynomialsort, moreobjs, moreorder);  timer(linearsort, moreobjs, moreorder);    // http://stackoverflow.com/a/6274381/635411  function shuffle(o) {    (var j, x, = o.length; i; j = math.floor(math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);    return o;  }    /**   * decorator function timing function.   * @param {function} f function timed.   */  function timer(f) {    console.time(f.name);    f.apply(null, [].slice.call(arguments, 1));    console.timeend(f.name);  }

100 "items:" polynomialsort: 1.893ms linearsort: 0.235ms 10000 "items:" polynomialsort: 1954.783ms linearsort: 2.205ms