Re: Insertion into sorted list

*To*: mathgroup at smc.vnet.net*Subject*: [mg71089] Re: Insertion into sorted list*From*: Bill Rowe <readnewsciv at sbcglobal.net>*Date*: Wed, 8 Nov 2006 06:06:59 -0500 (EST)

On 11/6/06 at 2:52 AM, andrew.j.moylan at gmail.com (Andrew Moylan) wrote: >I have a sorted List. I need to occasionally insert new elements, >while always keeping the list sorted. Is there a more efficient way >to do this than the most obvious way (calling Append then calling >Sort)? Probably. One approach might be to use Ordering to get the position a new element needs to be inserted in order to get a new sorted list with that element. For example, first generating a short sorted data set and a new element In[4]:= data=Sort@Table[Random[],{5}] Out[4]= {0.0707114,0.488412,0.634839,0.655525,0.999736} In[7]:= new=Random[] Out[7]= 0.561502 The position the new element needs to be in is given by In[8]:= order=Ordering@Flatten@{new,data} Out[8]= {2,3,1,4,5,6} Putting this all together In[9]:= data=#[[Ordering@#]]&@Flatten@{new,data} Out[9]= {0.0707114,0.488412,0.561502,0.634839,0.655525,0.999736} Alternatively, this same technique could be done as either data=#[[Ordering@#]]&@Append[data,new] or data=#[[Ordering@#]]&@Join[{new},data] I did some very quick testing on my machine which indicates doing data=#[[Ordering@#]]&@Join[{new},data] is somewhat faster than data=Sort@Append[data,new] when adding a single element. But if you need to add several elements it will definitely be faster to create add the all of the elements then sort using Ordering. -- To reply via email subtract one hundred and four