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:15:49 -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