I have a sorted JavaScript array, and want to insert one more item into the array such the resulting array remains sorted. I could certainly implement a simple quicksort-style insertion function:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.splice(locationOf(element, array) + 1, 0, element);
return array;
}
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (end-start <= 1 || array[pivot] === element) return pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
console.log(insert(element, array));
[WARNING] this code has a bug when trying to insert to the beginning of the array, e.g. insert(2, [3, 7 ,9]) produces incorrect [ 3, 2, 7, 9 ].
However, I noticed that implementations of the Array.sort function might potentially do this for me, and natively:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.push(element);
array.sort(function(a, b) {
return a - b;
});
return array;
}
console.log(insert(element, array));
Is there a good reason to choose the first implementation over the second?
Edit: Note that for the general case, an O(log(n)) insertion (as implemented in the first example) will be faster than a generic sorting algorithm; however this is not necessarily the case for JavaScript in particular. Note that:
- Best case for several insertion algorithms is O(n), which is still significantly different from O(log(n)), but not quite as bad as O(n log(n)) as mentioned below. It would come down to the particular sorting algorithm used (see Javascript Array.sort implementation?)
- The sort method in JavaScript is a native function, so potentially realizing huge benefits -- O(log(n)) with a huge coefficient can still be much worse than O(n) for reasonably sized data sets.
splice()(e.g. your 1st example) is already O(n). Even if it doesn't internally create a new copy of the entire array, it potentially has to shunt all n items back 1 position if the element is to be inserted in position 0. Maybe it's fast because it's a native function and the constant is low, but it's O(n) nonetheless. – DesertparseIntuseMath.floorinstead.Math.flooris much faster thanparseInt: jsperf.com/test-parseint-and-math-floor – Unalienablearray.push()always adds the new element at the end, so it doesn't need to reposition any existing elements. If the internal allocation size increases geometrically (e.g., doubling each time we run out of space), then insertions will be amortised O(1) time. – Desertarray.splice()necessarily has to move ( = copy) all elements to the right of the inserted element, and this necessarily takes time linear in the number of those elements.array.push()does not, because it needs to move ( = copy) zero such elements.array.push()might be implemented to always reallocate and copy, in which case it would indeed take linear time (in the length of the entire array) each time, but that would be a bad choice of implementation. – Desert