Databases
StackOverflow2013
Postsdbo
POEfficient way to insert a number into a sorted array of numbers?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient way to insert a number into a sorted array of numbers?
    primarykey
    data
    text
    <p>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:</p> <pre><code>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 &lt;= 1 || array[pivot] === element) return pivot; if (array[pivot] &lt; element) { return locationOf(element, array, pivot, end); } else { return locationOf(element, array, start, pivot); } } console.log(insert(element, array)); </code></pre> <p><strong>[WARNING]</strong> <em>this code has a bug when trying to insert to the beginning of the array, e.g. <code>insert(2, [3, 7 ,9]</code>) produces incorrect [ 3, 2, 7, 9 ].</em></p> <p>However, I noticed that implementations of the Array.sort function might potentially do this for me, and natively:</p> <pre><code>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)); </code></pre> <p>Is there a good reason to choose the first implementation over the second?</p> <p><strong>Edit</strong>: 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:</p> <ul> <li>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 <a href="https://stackoverflow.com/questions/234683/javascript-array-sort-implementation">Javascript Array.sort implementation?</a>)</li> <li>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. </li> </ul>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. US林果皞
    1. USElliot Kroo
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COusing splice in the second implementation is a bit wasteful. Why not use push?
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. USBreton
    2. COGood point, I just copied it from the first.
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. USElliot Kroo
    3. COAnything containing `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.
      singulars
      1. POEfficient way to insert a number into a sorted array of numbers?
      1. USj_random_hacker
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload