Mathematica 9 is now available
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: [mg71103] Re: Insertion into sorted list
  • From: "Andrew Moylan" <andrew.j.moylan at gmail.com>
  • Date: Wed, 8 Nov 2006 06:08:38 -0500 (EST)
  • References: <eimq10$9b7$1@smc.vnet.net>

Thanks for your replies. I've written a function 'InsertSorted' that
solves this problem using a binary search. Here's the usage string:

InsertSorted::usage = "InsertSorted[l, e]
    gives the sorted List l with e inserted such that the resulting
List is \
also sorted. InsertSorted[l, e, p] uses the ordering function p.";

And here's the function definition, which can be pasted into a new cell
in a Mathematica notebook:

\!\(\(InsertSorted[lst_List, e_, p_: \((OrderedQ[{#1, #2}] &)\)] :=
      Module[\[IndentingNewLine]{lower = 1,
          upper = Length[lst] + 1}, \[IndentingNewLine]While[
          lower \[NotEqual]
            upper, \[IndentingNewLine]\(With[{mid =
                  Floor[\(lower + upper\)\/2]},
\[IndentingNewLine]Print[
                p[lst\[LeftDoubleBracket]mid\[RightDoubleBracket],
                  e]]; \[IndentingNewLine]If[
                p[e, lst\[LeftDoubleBracket]
                    mid\[RightDoubleBracket]], \[IndentingNewLine]upper
=
                  mid, \[IndentingNewLine]lower =
                  mid + 1\[IndentingNewLine]];\[IndentingNewLine]];\)\
\[IndentingNewLine]]; \[IndentingNewLine]Insert[lst, e,
          lower]\[IndentingNewLine]];\)\)

I'm sorry to dsitribute the function in this slightly messy way. I also
have a notebook and associated automatically-generated .m file, which
represent a package "InsertSorted`" that can be placed in
Mathematica/Applications as usual and accessed via the Needs function.
Can anyone suggest the "correct" way to distribute such packages to any
users of this newsgroup who might be interested?

Cheers,
Andrew


On Nov 6, 6:59 pm, "Andrew Moylan" <andrew.j.moy... at gmail.com> wrote:
> Hi all,
>
> 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)?
> 
> Thanks for any help,
> 
> Andrew


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