Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1999
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1999

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

Search the Archive

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
>
> 


  • Prev by Date: Re: checking for overlap
  • Next by Date: Re: Q: NSolve with conditions
  • Previous by thread: Sorting problem
  • Next by thread: iMath integrates with MathScript