-1

There are two arrays of maps. The first array contains maps of ID values in a specific order (but not necessarily either pure ASC or DESC ordering):

// pseudo code
first := [
    {"id": 1},
    {"id": 2},
    {"id": 3}
]

...and an unsorted array of data with corresponding ID values, but not in the same ordering:

second := [
    {"id": 3, "text": "hello"},
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"}
]

How can I sort the second array such that its maps are in the same order as the first array via the matching ID values, while achieving the fastest code execution as possible?

(Note that the ordering of the first array is not known before runtime.)

The desired result in this case would be:

desiredResult := [
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"},
    {"id": 3, "text": "hello"}
]
5
  • I don't understand - you have the id in the second array already, why not just sort on that key since it's the same key sorting the first array? – Kevin Hsu Dec 4 '15 at 19:24
  • Because the order is not either simply either 'asc' or 'desc' by the ID for the second array. The order of the records in the second array is based on the location of the corresponding ID values in the first array. – Curtis La Graff Dec 4 '15 at 19:26
  • Any reason you can't just put the second array into a hash table/dictionary, with its id as a key, then iterate over your first array to get the values immediately into their proper location in your new array? Or what do you mean when you say "memory-optimized?" Do you mean in place? Or just "not super inefficient?" – enderland Dec 4 '15 at 19:28
  • What do you mean by "Optimized"? Do you want fast or space efficient? – Ampt Dec 4 '15 at 19:33
  • I've adjusted my question. I am seeking a solution that will provide the fastest code execution speed as possible. @enderland Using a hash-table/dictionary would work; I am just unsure if that is the best way to achieve the fastest execution speed for ordering. – Curtis La Graff Dec 4 '15 at 19:35
3

I'm going to assume that in the general case these ids might be strings and might be in a non-natural order in both first and second, since otherwise the trivial solutions suggested in the comments would be adequate.

One obvious solution is to walk through the lists linearly, rearranging the second array's elements along the way.

I assume this means that for each element in first, you do a linear search in second for the corresponding element and then insert it into the right position in result. This would be an O(n^2) algorithm.

I believe you can do this in O(n) by converting first into a map from id to index. So, assuming we start with this (I'll write Javascript since I'm better at that language, but I assume this works in Go too):

var first = [
  { "id": "biz" },
  { "id": "qux" },
  { "id": "foo" }
]

var second = [
  { "id": "foo", "text": "dabra" },
  { "id": "biz", "text": "abra" },
  { "id": "qux", "text": "ca" }
]

I would iterate over first to construct this map from ids to positions in the final array:

var idToPositionMap = {
  "biz": 0,
  "qux": 1,
  "foo": 2
}

Then I would iterate over second, using lookups in that map to insert items into the the result array:

second.map(function(item) {
   result[idToPositionMap[item.id]] = item;
});

Both of these steps should be O(n), assuming keyed lookup is O(1) and iterating over an array is O(n), like they should be, so total time is O(2n) = O(n).

I'm fairly sure O(n) is the best time complexity you can possibly get for this operation, since you need to touch every element of each array, so any further optimization would have to involve language-specific details and probably a lot of profiling.

Not the answer you're looking for? Browse other questions tagged or ask your own question.