home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3595 < prev    next >
Encoding:
Text File  |  1993-01-25  |  2.9 KB  |  63 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!gatech!hubcap!ncrcae!ncrhub2!ncrgw2!psinntp!bnlux1.bnl.gov!sscdaq.phy.bnl.gov!murphy
  3. From: murphy@sscdaq.phy.bnl.gov (Michael Murphy)
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <1993Jan25.224200.7195@bnlux1.bnl.gov>
  6. Sender: news@bnlux1.bnl.gov (Usenet news)
  7. Organization: Brookhaven National Laboratory  Upton, NY
  8. Date: Mon, 25 Jan 1993 22:42:00 GMT
  9. Lines: 52
  10.  
  11.  
  12. >jos@and.nl (Jos Horsmeier) writes:
  13.  
  14. >>In article <asean.727858796@armstrong.ecn.purdue.edu> asean@armstrong.ecn.purdue.edu (Sean Ahern) writes:
  15. >>|jagrant@emr1.emr.ca (John Grant) writes:
  16. >>|>Given an array of values, is it possible to find the maximum of
  17. >>|>the array and the next smallest value in a single pass?  The reason
  18. >>|>I want it in one pass, is that the array is actually a data file
  19. >>|>of a million float values.
  20. >>|
  21. >|If you were able to do this, the algorithm should be able to extend to the
  22. >|next smallest, and the next, with little or no trouble.
  23. >|
  24. >|But the requirement of the algorithm was to do this in one pass.  This would
  25. >|give us an O(n) sorting algorithm that works on arbitrary data.  I don't
  26. >|believe such an animal exists with only one processor.
  27. >
  28. >I beg to differ here. Lets do some big Oh calculations. Given n elements
  29. >in an array, one can find the maximum value in O(n) operations. One can 
  30. >find the next value in O(n) operations too, so both can be done in 
  31. >O(n)+O(n)= O(2*n) operations. But constants don't count here, so the
  32. >whole job can be done uisng O(n) operations. 
  33.  
  34. This is true, however the first and second largest (smallest) elements of 
  35. an array using can be computed using only n+lg(n)-1 comparisons.  For 
  36. n approximately equal to a million, this is about 1,000,020 comparisons as
  37. opposed to 2,000,000.  (Observe that as n increases the lg(n) term becomes 
  38. negligable).
  39.  
  40. (This was a homework problem in my algorithms course last year.  If nobody 
  41. gets it in a week, I'll post the solution).
  42.  
  43.  asean@armstrong.ecn.purdue.edu writes:
  44.  
  45. >I suppose a good way to find the k smallest elements of an array would be
  46. >to do a O(n*logn) sort and then pull off the smallest k elements.  Though I
  47. >must admit that if you only want the first 2 smallest, the O(2*n) algorithm
  48. >would be better for n>4.
  49.  
  50. The problem of finding the k-smallest elements of an array is often called 
  51. "Selection."  Algorithms exist that can perform Selection in guaranteed 
  52. linear time.  However they are more of theoretical importance than of practical
  53. concern because of restrictive constants inside of the big-O (see Corman, 
  54. Rivest, et al "Introduction to Algorithms" for a description of one such
  55. algorithm).  A practical Selection algorithm is nicely described in 
  56. Sedgewick's "Introduction to Algorithms."  The idea is based on the Quicksort 
  57. partitioning method.  In the average case, this algorithm runs in linear time, 
  58. but, like Quicksort, can be as bad as O(n^2) if the data is already in sorted 
  59. order.
  60.  
  61.  
  62. Michael Murphy
  63.