Insert Sort array of objects

Question

I have an array of nearly sorted ~1000 objects like {val: N} and sorting them by built-in Array.prototype.sort:

arr.sort(function(a, b) { return a.val - b.val });

I've stumble upon http://jsperf.com/javascript-sort/16 and tried to use Insert Sort:

for (i = 1; i < arr.length; i++) {
    var tmp = arr[i],
    j = i;
    while (arr[j-1].val > tmp.val) {
        arr[j] = arr[j-1];
        --j;
    }
    arr[j] = tmp;
}

but it always throws an error: TypeError: Cannot read property 'kills' of undefined.

Where to dig?

Thanks in advance.

lol! the performance numbers in jsperf.com/javascript-sort/16 are for a sorted array, for which this algorithm (unsurprisingly) takes linear time, instead of its well-known O(N^2) performance... — tucuxi
– tucuxi, Commented Jan 14, 2013 at 14:21

PRB · Accepted Answer · 2013-01-14 14:21:15Z

1

You are missing a bounds check on j in the loop:

while (j > 0 && arr[j-1].val > tmp.val) {
    arr[j] = arr[j-1];
    --j;
}

answered Jan 14, 2013 at 14:21

PRB

4842 silver badges5 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Insert Sort array of objects

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related