Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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