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. > anyone know the answer? > > Maths > >