Re: Sorting problem

• To: mathgroup at smc.vnet.net
• Subject: [mg20112] Re: [mg20071] Sorting problem
• From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
• Date: Thu, 30 Sep 1999 02:43:18 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```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: [mg20112] [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.