Menu
I would like to write a piece of code for inserting a number into a sorted array at the appropriate position (i.e. the array should still remain sorted after insertion)
My data structure doesn't allow duplicates.
I am planning to do something like this:
Is there any other better way?
720
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));
The bisect module provides us with the insort() function with which we can insert an element to a sorted list. The insort() method takes the sorted list as its first input argument and the element to be inserted as its second input argument. After execution, the element is inserted into the list.
If you really have an array and not a better data structure, that's optimal. If you're flexible on the implementation, take a look at AA Trees - They're rather fast and easy to implement. Obviously, takes more space than array, and it's not worth it if the number of elements is not big enough to notice the slowness of the blit as compared to pointer magic.
99
Does the data have to be sorted completely all the time? If it is not, if it is only necessary to access the smallest or highest element quickly, Binary Heap gives constant access time and logn addition and deletion time. More over it can satisfy your condition that the memory should be consecutive, since you can implement a BinaryHeap on top of an array (I.e; array[2n+1] left child, array[2n+2] right child).
28
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
