Insert json object to ordered array in javascript

Question

I have a array of ~2000 object like in this format:

[{
    "$order": 2998,
    "text": "Rosales Glenn",
    "id": 375
}, {
    "$order": 2999,
    "text": "Dillard Joyce",
    "id": 450
}, {
    "$order": 3000,
    "text": "Maryellen Hogan",
    "id": 365
}, {
    "$order": 3002,
    "text": "Jeannette Church",
    "id": 207
}]

I need to insert an object into the correct place in an efficient way: e.g:

{
    "$order": 3001,
    "text": "Jeannette Chichi",
    "id": 205
}

Assuming I don't need to overwrite an existing element (no duplicate "$order") when inserting the new one, anyone know a good and fast algorithm to insert the new object to the array using $order as the key? external libraries are also an option (if they support Angular). Thanks!

Doesnt work if the array begins with $order = 3002....

badigard
– badigard

2016-07-17 07:42:02 +00:00
Commented Jul 17, 2016 at 7:42 — badigard
– badigard, Commented Jul 17, 2016 at 7:42

Nina Scholz · Accepted Answer · 2016-07-17 08:37:52Z

At least you need to iterate until the index is found.

var array = [{ "$order": 2998, "text": "Rosales Glenn", "id": 375 }, { "$order": 2999, "text": "Dillard Joyce", "id": 450 }, { "$order": 3000, "text": "Maryellen Hogan", "id": 365 }, { "$order": 3002, "text": "Jeannette Church", "id": 207 }],
    insert = { "$order": 3001, "text": "Jeannette Chichi", "id": 205 },
    index = -1;

array.some(function (a,i) {
    if (a.$order > insert.$order) {
        return true;
    }
    index = i;
});

array.splice(index + 1, 0, insert);

console.log(array);

Or as suggested, you could use a binary search for it.

function search(array, insert, cb) {
    var left = -1,
        right = array.length,
        actual;

    while (left !== right && left + 1 !== right) {
        actual = Math.floor((left + right) / 2);
        if (cb(array[actual]) < cb(insert)) {
            left = actual;
            continue;
        }
        if (cb(array[actual]) > cb(insert)) {
            right = actual;
        }
    }
    return left;
}

var array = [{ "$order": 2998, "text": "Rosales Glenn", "id": 375 }, { "$order": 2999, "text": "Dillard Joyce", "id": 450 }, { "$order": 3000, "text": "Maryellen Hogan", "id": 365 }, { "$order": 3002, "text": "Jeannette Church", "id": 207 }],
    insert = { "$order": 3001, "text": "Jeannette Chichi", "id": 205 },
    index = search(array, insert, function (a) { return a.$order; });

array.splice(index + 1, 0, insert);
console.log(array);

sielakos · Accepted Answer · 2016-07-17 07:39:44Z

2

It does not look like you can go below complexity of splice implementation and that depends on engine.

What you can optimize is your search algorithm. I would go for binary search.

edit for more info on binary search see http://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm

answered Jul 17, 2016 at 7:39

sielakos

2,40413 silver badges13 bronze badges

Collectives™ on Stack Overflow

Insert json object to ordered array in javascript

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related