MathGroup Archive 1999

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

Search the Archive

Re: Sorting problem

  • To: mathgroup at
  • Subject: [mg20158] Re: [mg20071] Sorting problem
  • From: "Andrzej Kozlowski" <andrzej at>
  • Date: Sat, 2 Oct 1999 03:05:12 -0400
  • Sender: owner-wri-mathgroup at

I agree. However my point was different. I meant conditions like "n + lg(n)
- 2 comparisons" are not really very relevant in the case of Mathematica
programming since we really can't control what goes on internally. On  the
other hand I now believe the author of the message was not interested in a
Mathematica program, just the algorithm. The standard thing to do in such
cases is first to check Knuth's book. This algorithm is in fact pretty
obvious; it is the proof that there can't be a better one that is
interesting. But this has even less to do with Mathematica.
Andrzej Kozlowski
Toyama International University

>From: kewjoi at (Kew Joinery)
>To: Andrzej Kozlowski <andrzej at>, "mathgroup at"
<mathgroup at>
>Subject: [mg20158] Re: [mg20071] Sorting problem
>Date: Fri, 01 Oct 1999 01:28:43 +0200

> Hello,
> 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
> 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 fr
> updated Combinatorica package.)
> *this is the build-in Stirling(2) code:
> In[2]:=
> StirlingS2[1234,100];//Timing
> Out[2]=
> {33.34 Second,Null}
> **this is the custom implementation:
> In[3]:=
> Stirling2[1234,100];//Timing
> Out[3]=
> {0.33 Second,Null}
> and the code was:
> In[1]:=
> Stirling2[n_Integer?Positive, k_Integer] :=
>   Sum [ (-1)^(k-i)*Binomial [k, i]*(i^n), {i, 1, k}]/k!
> Eugene.
> 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: [mg20158] [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: Preventing plotting on output
  • Next by Date: RE: greek alphabet
  • Previous by thread: Re: Preventing plotting on output
  • Next by thread: Re: Sorting problem