home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3577 < prev    next >
Encoding:
Text File  |  1993-01-24  |  2.3 KB  |  48 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!linac!att!news.cs.indiana.edu!noose.ecn.purdue.edu!armstrong.ecn.purdue.edu!asean
  3. From: asean@armstrong.ecn.purdue.edu (Sean Ahern)
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <asean.727916943@armstrong.ecn.purdue.edu>
  6. Sender: news@noose.ecn.purdue.edu (USENET news)
  7. Organization: Purdue University Engineering Computer Network
  8. References: <1993Jan24.040702.6193@emr1.emr.ca> <asean.727858796@armstrong.ecn.purdue.edu> <4400@dozo.and.nl>
  9. Date: 24 Jan 93 23:09:03 GMT
  10. Lines: 36
  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. 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.
  36.  
  37. I went through this same argument with myself as I went to bed and
  38. realized my mistake.
  39.  
  40. I suppose a good way to find the k smallest elements of an array would be
  41. to do a O(n*logn) sort and then pull off the smallest k elements.  Though I
  42. must admit that if you only want the first 2 smallest, the O(2*n) algorithm
  43. would be better for n>4.
  44.  
  45. --
  46. Sean Ahern-------------------ahern@purdue.edu-----------------Purdue University
  47. My name is Batman.  You killed my father.  Prepare to die.
  48.