home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16641 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.2 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!stanford.edu!agate!spool.mu.edu!darwin.sura.net!wupost!uwm.edu!rpi!batcomputer!munnari.oz.au!goanna!ok
  2. From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: qucik, merge, shell and bubble sort
  5. Message-ID: <15985@goanna.cs.rmit.oz.au>
  6. Date: 17 Nov 92 04:55:48 GMT
  7. References: <1e1cnvINNt2t@usenet.INS.CWRU.Edu>
  8. Organization: Comp Sci, RMIT, Melbourne, Australia
  9. Lines: 38
  10.  
  11. In article <1e1cnvINNt2t@usenet.INS.CWRU.Edu>, cc015@cleveland.Freenet.Edu (Vito T. Kwan) writes:
  12. > Hi all,
  13. >     I want to take a look at these four sorting method in C, does anyone
  14. > know where can I get (ftp) them?
  15. >     Thankss in advance
  16.  
  17. Costs:
  18.     Bubble sort is O(N**2).  It has no known uses.  It is bad even for
  19.     an O(N**2) algorithm; if you want a very simple sorting algorithm
  20.     you can remember and that will work well, pick insertion sort.
  21.  
  22.     Shell sort is O(N**1.5) -ish.  It has no special advantages.
  23.  
  24.     Quick sort is O(N**2) in the worst case.  It is complicated and
  25.     unstable.  Its _average_ cost is O(N.lgN).  The only known reason
  26.     for using quicksort is if you are DESPERATELY short of memory; it
  27.     was invented for use on a computer with 256 words of main memory.
  28.     (Read Hoare's paper in Computer Journal 1961.)  At the time it was
  29.     invented, it was known to be inferior to merge sort by every metric
  30.     except space, and if you are sorting a list it doesn't save any
  31.     space either.
  32.  
  33.     Merge sort is O(N.lgN) in the worst cast.  If the comparisons are
  34.     not trivial (i.e. if the compiler does not know at compile time that
  35.     they are machine integer comparisons) then the *worst* case of
  36.     merge sort is better than the *best* case of quick sort.
  37.  
  38. Of the four methods, the only one that can be recommended for general use
  39. is merge sort.  If you have to write a sort routine for an embedded controller
  40. or some other application where there is almost no main memory and no backing
  41. store, quick sort is useful.  For everyday programming in C, you should try
  42. using the built-in qsort() function.  Most C libraries I have come across use
  43. some version of quick-sort, which makes them rather slow, but at least it is
  44. there and debugged.
  45.  
  46. Your best source of such algorithms would be a textbook like
  47. Sedgewick's "Algorithms in C".
  48.  
  49.