home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / games / programm / 4702 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.6 KB
  1. Path: sparky!uunet!munnari.oz.au!bunyip.cc.uq.oz.au!uqcspe!cs.uq.oz.au!warwick
  2. From: warwick@cs.uq.oz.au (Warwick Allison)
  3. Newsgroups: rec.games.programmer
  4. Subject: Re: Advice needed for fastest sort algorthm
  5. Message-ID: <11056@uqcspe.cs.uq.oz.au>
  6. Date: 16 Nov 92 02:37:32 GMT
  7. References: <6759@news.duke.edu> <BxD5pt.DyI@news.cso.uiuc.edu> <BxG0MC.7yK@chinet.chi.il.us> <10991@uqcspe.cs.uq.oz.au> <1drd06INNnji@calvin.usc.edu>
  8. Sender: news@cs.uq.oz.au
  9. Reply-To: warwick@cs.uq.oz.au
  10. Lines: 29
  11.  
  12. dank@calvin.usc.edu (Dan King) writes:
  13.  
  14. >Quoting from The Art of Computer Programming, Volume 3 (pp176-178):
  15. >"[r]adix sorting is usually more efficient than any other known
  16. >sorting method for internal sorting."
  17.  
  18. Is that the first edition (1968), or second edition (1973).
  19. I hope the references haven't dated too much :-).
  20.  
  21. Seriously, it's these exact statement that I'm arguing against.  Saying that ANY
  22. algorithm for sorting is the best, or "usually more efficient than any other" is
  23. simply crazy.  Each algorithm has strengths and weaknesses.  Radix sort isn't
  24. even APPLICABLE in most cases.
  25.  
  26.  
  27. >Speaking about his example program, Knuth says,
  28. >"A p-pass version of the program would take (11p-1)N+O(pM) units of
  29. >time." [p is the number of keys and M is the number of radix piles]
  30.  
  31. ie. if p is too large, forget it.  too large = O(N)... or even O(sqrt(N)).
  32. (where N is the EXPECTED number of items for sorting)
  33.  
  34. --
  35. Warwick
  36. --
  37.   _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
  38.  /     * <-- Computer Science Department,  /  
  39.  \_.-._/     University of Queensland,    /   C references are NULL && void*
  40.       v      Brisbane, Australia.        /  
  41.