home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3568 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  2.0 KB
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.programming
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <4400@dozo.and.nl>
  6. Date: 24 Jan 93 12:49:32 GMT
  7. References: <1993Jan24.040702.6193@emr1.emr.ca> <asean.727858796@armstrong.ecn.purdue.edu>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 45
  10.  
  11. In article <asean.727858796@armstrong.ecn.purdue.edu> asean@armstrong.ecn.purdue.edu (Sean Ahern) writes:
  12. |jagrant@emr1.emr.ca (John Grant) writes:
  13. |>Given an array of values, is it possible to find the maximum of
  14. |>the array and the next smallest value in a single pass?  The reason
  15. |>I want it in one pass, is that the array is actually a data file
  16. |>of a million float values.
  17. |>
  18. |>If so, I guess the same single pass could also find the min and next
  19. |>highest value too?
  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. Finding three elements,
  33. takes O(3*n)= O(n) operations, and so on. But sorting all n elements
  34. this way takes up O(n*n) operations, which is, in fact, quite a lousy
  35. way of sorting an array. But lets get back to the original problem,
  36. here is a simple solution:
  37.  
  38. m1 = a[1]            // m1 >= m2 
  39. m2 = a[1]
  40.  
  41. loop: i = 2 .. n        // compare a[i], m1 and m2
  42.  
  43.     if a[i] > m2 then    // is it a candidate?
  44.         m2 = a[i]
  45.  
  46.     if m2 > m1 then        // is it the largest?
  47.         swap m1, m2    
  48.  
  49. result: m1, m2
  50.  
  51. I hope this clarifies things a bit,
  52.  
  53. kind regards,
  54.  
  55. Jos aka jos@and.nl
  56.