Re: Sorting problem

• To: mathgroup at smc.vnet.net
• Subject: [mg20158] Re: [mg20071] Sorting problem
• From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
• Date: Sat, 2 Oct 1999 03:05:12 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```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
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp

----------
>From: kewjoi at hixnet.co.za (Kew Joinery)
>To: Andrzej Kozlowski <andrzej at tuins.ac.jp>, "mathgroup at smc.vnet.net"
<mathgroup at smc.vnet.net>
>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
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 fr
om
the
> 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
>> JAPAN
>> http://sigma.tuins.ac.jp
>> http://eri2.tuins.ac.jp
>>
>> ----------
>> >From: Cheng Tsz Hei <s986001 at mailserv.cuhk.edu.hk>
To: mathgroup at smc.vnet.net
>> >To: mathgroup at smc.vnet.net
>> >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