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:14:22 -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

```

• Prev by Date: Re: Possible simple bug in NMaximize
• Next by Date: Re: Insertion into sorted list
• Previous by thread: Re: Insertion into sorted list
• Next by thread: Re: Insertion into sorted list