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