home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / games / programm / 4715 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.6 KB  |  40 lines
  1. Newsgroups: rec.games.programmer
  2. Path: sparky!uunet!wupost!darwin.sura.net!sgiblab!munnari.oz.au!bruce.cs.monash.edu.au!alanf
  3. From: alanf@cs.monash.edu.au (Alan Grant Finlay)
  4. Subject: Re: Advice needed for fastest sort algorthm
  5. Message-ID: <alanf.721969869@bruce.cs.monash.edu.au>
  6. Sender: news@bruce.cs.monash.edu.au (USENET News System)
  7. Organization: Computer Science, Monash University, Australia
  8. References: <BxG0MC.7yK@chinet.chi.il.us> <10991@uqcspe.cs.uq.oz.au> <1992Nov11.043526.26732@netcom.com> <1992Nov11.161052.5552@panther.mot.com>
  9. Date: Tue, 17 Nov 1992 03:11:09 GMT
  10. Lines: 28
  11.  
  12. asu@panther4.panther.mot.com (Russ Trotter) writes:
  13.  
  14. >I hate to jump on this seemingly runaway train but.... 
  15.  
  16. >In one of my classes, I remember the teacher saying that it
  17. >had been proven that O(n log n) was the best one could do
  18. >for _comparison_ based sorting...  Is this a more correct assertion?
  19.  
  20. >I don't know much (at all :) ) about Radix sort  (only how to spell it :) )
  21. >so I can't be sure if it disproves the statement above.
  22.  
  23. The problem with this question is that it is a non-question.
  24. Its like asking what is the worlds fastest dishwasher.
  25. Its depends upon the data and what you mean by fast.
  26.  
  27. Do you want fastest worst case, fastest average case, fastest "usually" case,
  28. or fastest best case?
  29.  
  30. Do you mind if the algorithms worst case time happens when the input data
  31. is already sorted?
  32.  
  33. What kind of machine architecture are you permitted to use.
  34.  
  35. How much data is there (an O(n^2) sort will beat most O(n log(n)) sorts
  36. on less than a score or so of elements)?
  37.  
  38. Is the range of values being sorted small enough to fit in real or
  39. virtual memory?
  40.