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

Question

I have an array of objects similar to this:

[
  {
    ref: "CTB98",
    name: "Joe"      
  },
  {
    ref: "HTF76",
    name: "Alice"      
  },
  {
    ref: "JHU90",
    name: "Tom"      
  },
  {
    ref: "ADF56",
    name: "Mary"      
  }
]

And in another array I have the exact order that they are meant to be in, referenced by their ref property:

["JHU90", "HTF76", "CTB98", "ADF56"]  

I'd like to rearrange the order of the first array of objects, so that the ref values on each object follow the same order as the values in my reference array above.

I'm new to computer science, so I will select the answer with best explanation of the technique.

Answer 1

This one is more preferable, in case when objects and referrers could be not matched.

function sortBy( items , ids ){

    let hash = {};
    let i = 0;

    for( i = 0; i <  items.length; i++ ){
        hash[ items[i].ref ] = items[i];
    }

    let orderedItems = [];
    for( i = 0; i <  ids.length; i++ ){
        if( hash[ids[i]]  ){
            orderedItems.push(hash[ids[i]]);
        }
    }

    return orderedItems;
}

Answer 2

I think you want to create a hash of your objects indexed by ref to prevent O(n^2) time.

This method will let you reorder in O(n) time at the 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 that involve indexOf or nested for loops / .forEach will cause the amount of time required to increase in a quadratic fashion O(n^2). For each of n element you may need to perform n operations.

Creating a hash object that uses each object's ref property as a key for the object allows looking up an object by ref to be a constant time operation, O(1). Creation of the hash is done in linear time, O(n), because insertion into the hash object is O(1) performed n times.

After the hash is made, you perform another O(n) operation by iterating your "order" array of n items, doing a O(1) lookup for each order key to get the final array.

So the overall time complexity of this method will be O(2n) which is still O(n).

This is a simplified explanation, not taking into account that hash table insertion is 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 = [];

for (var i = 1; i < 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 = [];

for (var i = 1; i < 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) {
  for (var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
  return o;
}

/**
 * Decorator function for timing a function.
 * @param {Function} f Function to be 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

Answer 3

When you are sorting, two items in the array will be picked and they will be compared to decide which should come first. In this case, the comparison has to happen between the index of the elements in references array. So, you can sort them like this

var data = [{ref: "CTB98", name: "Joe"},
            {ref: "HTF76", name: "Alice"},
            {ref: "JHU90", name: "Tom"},
            {ref: "ADF56", name: "Mary"}],
    references = ["JHU90", "HTF76", "CTB98", "ADF56"];

data.sort(function (item1, item2) {
    // Index of `item1.ref` in `references` and index of `item2.ref` in 
    // `references` are used to decide.
    return references.indexOf(item1.ref) - references.indexOf(item2.ref);
});

console.log(data);

Output

[ { ref: 'JHU90', name: 'Tom' },
  { ref: 'HTF76', name: 'Alice' },
  { ref: 'CTB98', name: 'Joe' },
  { ref: 'ADF56', name: 'Mary' } ]

Note: Since you are very new, I would recommend reading this wonderful answer. That explains why we are subtracting the index values and what should we return from the function which compares the elements.

Answer 4

This method is a little finnicky, but it works because it depends on the principle that JavaScript's Array.prototype.forEach will iterate over elements in index order (see the jsfiddle):

var objs = [
      {
        ref: "CTB98",
        name: "Joe"      
      },
      {
        ref: "HTF76",
        name: "Alice"      
      },
      {
        ref: "JHU90",
        name: "Tom"      
      },
      {
        ref: "ADF56",
        name: "Mary"      
      }
    ],
    order = ["JHU90", "HTF76", "CTB98", "ADF56"],
    arr = [];

order.forEach(function(key) {
    objs.forEach(function(o) {
        if(o.ref === key) {
            arr.push(o);   
        }
    });
});

console.log(arr);

Output: