Thursday, September 9, 2010

Javascript insort function

I recently had the need for some sorted insertion in Javascript arrays, thought I'd share this tiny bit of code:


Array.prototype.bisect = function(x, lo, hi) {
var mid;
if(typeof(lo) == 'undefined') lo = 0;
if(typeof(hi) == 'undefined') hi = this.length;
while(lo < hi) {
mid = Math.floor((lo + hi) / 2);
if(x < this[mid]) hi = mid;
else lo = mid + 1;
}
return lo
}

Array.prototype.insort = function(x) {
this.splice(this.bisect(x), 0, x);
}


Of course, these methods only work on an already sorted (or empty) array, so if you're using them on an array that came from elsewhere, sort it first. But once sorted, these insertions will maintain the sortedness, no need to 'push' and 'sort' every time you need to insert something into a sorted array.

(lo and hi parameters are optionally possible for the bisection method to allow restricted searches)

No comments: