home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16652 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.3 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!sun-barr!cs.utexas.edu!usc!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: <15988@goanna.cs.rmit.oz.au>
  6. Date: 17 Nov 92 09:04:30 GMT
  7. References: <1e1cnvINNt2t@usenet.INS.CWRU.Edu> <15985@goanna.cs.rmit.oz.au>
  8. Organization: Comp Sci, RMIT, Melbourne, Australia
  9. Lines: 42
  10.  
  11. I thought I had better back up this posting with some numbers:
  12. > In article <1e1cnvINNt2t@usenet.INS.CWRU.Edu>, cc015@cleveland.Freenet.Edu (Vito T. Kwan) writes:
  13. > Costs:
  14. >     Quick sort is O(N**2) in the worst case.  It is complicated and
  15. >     unstable.  Its _average_ cost is O(N.lgN).  The only known reason
  16. >     for using quicksort is if you are DESPERATELY short of memory; it
  17. >     was invented for use on a computer with 256 words of main memory.
  18. >     (Read Hoare's paper in Computer Journal 1961.)  At the time it was
  19. >     invented, it was known to be inferior to merge sort by every metric
  20. >     except space, and if you are sorting a list it doesn't save any
  21. >     space either.
  22. > 
  23. >     Merge sort is O(N.lgN) in the worst cast.  If the comparisons are
  24. >     not trivial (i.e. if the compiler does not know at compile time that
  25. >     they are machine integer comparisons) then the *worst* case of
  26. >     merge sort is better than the *best* case of quick sort.
  27. > 
  28. > Of the four methods, the only one that can be recommended for general use
  29. > is merge sort.
  30.  
  31. The following numbers were obtained on an Encore Multimax running their
  32. port of System V Release 3.2, using Encore's C compiler (-q optimize=time)
  33. and runtime library.  File 1 was 25000 words in random order (taken from
  34. /usr/dict/words on another Encore box running BSD).  File 2 was the same
  35. 25000 words replicated 4 times and scrambled again.  All times are accurate
  36. to about +/- 1 second.
  37.  
  38.                 File 1        File 2
  39.  
  40. merge sort (array based)    4 seconds    20 seconds
  41. qsort                6 seconds    24 seconds
  42. heap sort (array based)        6 seconds    29 seconds
  43. dummy (read, no sort, write)    2 seconds     8 seconds
  44.  
  45. From these figures, the actual sorting times were
  46.  
  47. merge sort (array based)    2 seconds    12 seconds
  48. qsort                4 seconds    16 seconds
  49. heap sort (array based)        4 seconds    21 seconds
  50.  
  51. This is not entirely fair to qsort, but on the other hand, I didn't pick
  52. my fastest version of merge sort either.
  53.