home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3590 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.7 KB
  1. Path: sparky!uunet!mcsun!uknet!edcastle!dcs.ed.ac.uk!pdc
  2. From: pdc@dcs.ed.ac.uk (Paul Crowley)
  3. Newsgroups: comp.programming
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <C1FE09.An2@dcs.ed.ac.uk>
  6. Date: 25 Jan 93 19:55:20 GMT
  7. References: <1993Jan24.040702.6193@emr1.emr.ca> <51915@seismo.CSS.GOV> <hjv.727890482@groucho.phil.ruu.nl>
  8. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  9. Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
  10. Organization: Edinburgh University
  11. Lines: 28
  12.  
  13. If comparisons are more expensive than other operations and you have to
  14. do this frequently on a big array, there is a standard algorithm that
  15. only uses (n + ceil(lg n) -1)) comparisons.  Supposing, for example,
  16. that the data objects are Word Tennis players and a comparison is a game
  17. of Word Tennis; then comparisons are *very* expensive to do compared to
  18. all other computations.  You play people off against each other in
  19. standard playoffs, like this:
  20.  
  21.      !
  22.    /   \
  23.   !     ?
  24.  / \   / \
  25. ?   ! *   *
  26.  
  27. Let ! be the player who won (which is why ! is shown at the top of every
  28. triangle because ! wins every game ! plays.)  ! is the maximum element. 
  29. There are two players who could be in second place, and they are marked
  30. with a question mark.  In general, there are ceil(lg n) of them.
  31.  
  32. I can't think offhand of an efficient way of implementing this, but I'm
  33. sure someone can.
  34.  
  35. For finding max and min simultaneously, there's a simple optimisation: 
  36. compare elements in pairs before comparing to stored max and min
  37. elements.  This takes floor((3n-4)/2) comparisons.
  38.   __                                  _____
  39. \/ o\ Paul Crowley   pdc@dcs.ed.ac.uk \\ //
  40. /\__/ Trust me. I know what I'm doing. \X/ 
  41.