MathGroup Archive 1999

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

Search the Archive

Re: Sorting problem

  • To: mathgroup at
  • Subject: [mg20156] Re: [mg20071] Sorting problem
  • From: kewjoi at (Kew Joinery)
  • Date: Sat, 2 Oct 1999 03:05:11 -0400
  • References: <7sv0o6$>
  • Sender: owner-wri-mathgroup at

With all the respect to Mr. Kozlowski?s words just to add this:
Sometimes even from innocent posting one could learn something new and
interesting (example- Langford problem), or probably find faster algorithm from
old book.
Here is an example when build-in function is much slower then custom
implementation using well-known formula from old book:(I took the code from the
updated Combinatorica package.)

*this is the build-in Stirling(2) code:

{33.34 Second,Null}

**this is the custom implementation:
{0.33 Second,Null}

and the code was:
Stirling2[n_Integer?Positive, k_Integer] :=
  Sum [ (-1)^(k-i)*Binomial [k, i]*(i^n), {i, 1, k}]/k!


Andrzej Kozlowski wrote:

> I don't want to sound rude but I do not think this problem is really so
> interesting or very relevant to this group. Or rather, more precisely, this
> kind of questions surface here from time to time but usually lead to
> anything fruitful. The reasons are as follows.
> There is nothing at all mysterious about the theoretical question itself. It
> is very well known and discussed in detail in Section 5.3.3 of Volume 3 of
> Knuth's "The Art of Computer Programming" (1973 edition). The method is
> described in Section 5.2.3 and called "tree selection". (the algorithm
> itself is on page 142). This can be easily implemented in Mathematica but it
> seems to me that is not much point doing so. The reason is that the actual
> function you will get will almost certainly perform worse in real life than
> something constructed using built in functions, even if it's theoretical
> running time of the algorithm is worse. For example, here is one obvious
> attempt:
> In[1]:=
> secondlargest[l_] := Max[DeleteCases[l, Max[l]]]
> It seems to me that this should have the worst case running time of 3n-3,
> but most likely will beat a user defined implementation of the best
> algorithm. And if not than probably something similar will. It may be mildly
> interesting to check this hypothesis but I have seen already enough evidence
> that this sort of thing is true in general. Of course there is another
> possible question here: would it be useful to have a built in implementation
> of a (generalized) algorithm of this type? I guess it probably just wouldn't
> be useful enough.
> In my opinion Mathematica has to be treated as a separate computing paradigm
> and efficiency comparisons only make sense between different Mathematica
> functions based on actual performance (which in any case may be platform
> dependent).
> --
> Andrzej Kozlowski
> Toyama International University
> ----------
> >From: Cheng Tsz Hei <s986001 at>
To: mathgroup at
> >To: mathgroup at
> >Subject: [mg20156] [mg20071] Sorting problem
> >Date: Wed, Sep 29, 1999, 16:33
> >
> > Dear everybody,
> >      Here I have some interesting problem want to share with everyone.
> > The problem is :
> >        there are n elements in the arrays and we would like to find the
> > second smallest
> > one in at most n + lgn - 2 comparsion in the worest case.
> >       anyone know the answer?
> >
> > Maths
> >
> >

  • Prev by Date: Re: greek alphabet
  • Next by Date: RE: creating input cell with unevaluated expression?
  • Previous by thread: Re: Sorting problem
  • Next by thread: Re: Re: List-Selection