Code to find position of number inside sorted array after selection sort isn't stable?

71 views Asked by At

This code sorts the array after inserting another element and returns the index of the inserted element in the sorted array (the first position or lowest possible index needs to be returned).

CODE:

function getIndexToIns(arr, num) {
  // Find my place in this sorted array.
  var sortedarr = sort(combinelists(arr, num).sort());
  var pos = [];
  for (i = 0; i < sortedarr.length; i++) {
    if (sortedarr[i] == num) {
      pos.push(i);
    }
  }
  return pos[0];
}

function combinelists(arr1, arr2) {
  var newarr = [];
  newarr.push(arr2);
  for (i = 0; i < arr1.length; i++) {
    newarr.push(arr1[i]);
  }
  return newarr;
}

function sort(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    var l = arr.length / 2;
    var leftarr = arr.slice(0, l);
    var rightarr = arr.slice(l);
    return combine(sort(leftarr), sort(rightarr));
  }
}

function combine(array, another_array) {
  var result = [];
  while (array.length && another_array.length) {
    if (array[0].age <= another_array[0].age) {
      result.push(array.shift());
    } else {
      result.push(another_array.shift());
    }
  }

  while (array.length)
    result.push(array.shift());

  while (another_array.length)
    result.push(another_array.shift());
  return result;
}

console.log(getIndexToIns([2, 20, 10], 19));
console.log(getIndexToIns([2, 5, 10], 15));

But it doesn't seem to work for all inputs:

It works for the following tests: 
[10, 20, 30, 40, 50], 30
[40, 60], 50
[2, 20, 10], 19

But it doesn't work for these:
[2, 5, 10], 15
[5, 3, 20, 3], 5
[3, 10, 5], 3
[10, 20, 30, 40, 50], 35

What's broken?

1

There are 1 answers

1
Nina Scholz On BEST ANSWER

You use Array#sort() without compareFunction, that means you get a result which every element is treated as string and not as number. That results, probably, to the wrong index.

var sortedarr = sort(combinelists(arr,num).sort());
//                                         ^^^^^^

You coud use a callback like

var sortedarr = sort(combinelists(arr,num).sort(function (a, b) { return a - b; }));

for sorting by numbers.