insert item in javascript array and sort

Question

Let's say I have an array

var test = new Array()

the values in test are 3,6,9,11,20

if I then have a variable

var id = 5

how can I insert 5 between 3 and 6 in the array? or do I just insert it wherever and then sort the array?

Thanks in advance.

edit:

I have the following code:

function gup( filter )
{
  filter = filter.replace(/[\[]/,"\\\[").replace(/[\]]/,"\\\]");
  var regexS = "[\\?&]"+filter+"=([^&#]*)";
  var regex = new RegExp( regexS );
  var results = regex.exec( window.location.href );
  if( results == null )
    return "";
  else
    return results[1];
}

var queryString = gup("SelectedID");


var hrefs = new Array();
$('.table404').children().children().each(function(){
var link = ($(this).find('a').attr('href'));
var startIndex = link.indexOf(",'");
var endIndex = link.indexOf("');");
if ( startIndex >= 0 && endIndex >= 0 ) {
var linkID = link.substring( startIndex+2, endIndex );
hrefs.push(linkID);
hrefs.push(queryString);
hrefs.sort()
}
alert(hrefs);
});

for each item inserted into the array I get an alert with the ID but for every item I get one 1 (the current queryString value), so the last pop up looks something like 1,1,1,1,1,2,4,6,7,8

Why do I get a new pop up for every item inserted into the array? I get the querystring value once for every other item inserted into the array. What do I have to do to get one pop up with the complete array?

Answer 1

You can use a binary searach to find an insertion point, if you array is large enough: Below is a quick code with tests. (Warning: not thoroughly tested). Also the array has to be a sorted array. Once you have an insertion point, just use the Array.splice function to insert at that index.

/**
 * Find insertion point for a value val, as specified by the comparator 
 * (a function)
 * @param sortedArr The sorted array
 * @param val The value for which to find an insertion point (index) in the array
 * @param comparator The comparator function to compare two values
 */
function findInsertionPoint(sortedArr, val, comparator) {   
   var low = 0, high = sortedArr.length;
   var mid = -1, c = 0;
   while(low < high)   {
      mid = parseInt((low + high)/2);
      c = comparator(sortedArr[mid], val);
      if(c < 0)   {
         low = mid + 1;
      }else if(c > 0) {
         high = mid;
      }else {
         return mid;
      }
      //alert("mid=" + mid + ", c=" + c + ", low=" + low + ", high=" + high);
   }
   return low;
}

/**
 * A simple number comparator
 */
function numComparator(val1, val2)  {
   // Suggested b @James
   return val1 - val2;
}

// TESTS --------------------------------

var arr = [0,1,3,6,9,11,20];
var idx = findInsertionPoint(arr, 2, numComparator);
arr.splice(idx, 0, 2);
alert(arr); // will alert [0,1,2,3,6,9,11,20]

var arr2 = [0,1,3,6,9,11,20];
var idx2 = findInsertionPoint(arr2, -1, numComparator);
arr2.splice(idx2, 0, -1);
alert(arr2); // will alert [-1,0,1,3,6,9,11,20]

If you have different objects, the only thing you need to do is provide appropriate comparator function.

Or if the array is really small and if you are especially lazy today, you can just do:

test.push(2).sort();

test.push(2); test.sort();