home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16707 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  7.2 KB
  1. Path: sparky!uunet!ontek!mikey
  2. From: mikey@ontek.com (euphausia superba)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: qucik, merge, shell and bubble sort
  5. Message-ID: <2188@ontek.com>
  6. Date: 17 Nov 92 22:33:48 GMT
  7. References: <1e1cnvINNt2t@usenet.INS.CWRU.Edu>
  8. Organization: Ontek Corporation -- Laguna Hills, California
  9. Lines: 159
  10.  
  11. In comp.lang.c, cc015@cleveland.Freenet.Edu (Vito T. Kwan) writes:
  12. | 
  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.  
  16. I have implementations of quick, merge, and bubble sort; send 
  17. email to me if you can't find them through other channels.
  18.  
  19. Many people have posted timings for sort routines over the
  20. years; I was dissatisfied with the level of detail, so I grabbed
  21. a few sort routines and did some hacking and measured some
  22. of the not-so-obvious aspects of how sort algorithms perform
  23. under extreme conditions.  This is scientific only in the
  24. sense that the numbers I got were repeatable to one or two
  25. significant digits.  
  26.  
  27. The columns in the following tables have these meanings:
  28.  
  29.   compares: Number of callbacks to the comparison function.
  30.         On the few occasions I've gprof'd a sort operation, most 
  31.         of the time is spent in the comparison function, so I 
  32.         consider this the most interesting column.
  33.  
  34.   stack:    Amount of stack space used (roughly).
  35.         Obviously, the way I measured this was non-portable,
  36.  
  37.   heap:     Amount of heap space used as reported by mallinfo.uordblks
  38.  
  39.   user:     User time as reported by times(tms.tms_utime)
  40.         This is supposed to be accurate to 1/60th of a second.
  41.  
  42.   system:   System time as reported by times(tms.tms_stime)
  43.         This is also supposed to be accurate to 1/60th of a second.
  44.  
  45. The rows describe the input array and the behavior of the 
  46. comparison function.
  47.  
  48.   random:   The input data is generated by rand(), and the 
  49.         comparison function reports truthfully.
  50.  
  51.   ascend:   The data being sorted is already in the correct
  52.         order.  This is a useful case for sorting
  53.         indexes which are pretty much already in order;
  54.         bubble sort handles this case well, but results
  55.         of bubble sort are excluded here, mostly because
  56.         bubble sort is silly.
  57.  
  58.   descend:  The input data is exactly in reverse order.
  59.  
  60.   fib asc:  The data is random, but the comparison function
  61.         always says that its first argument is less than
  62.         its second argument.
  63.  
  64.   fib asc:  The data is random, but the comparison function
  65.         always says that its first argument is greater than
  66.         its second argument.
  67.  
  68.   suprise:  The comparison function returns a random value.
  69.  
  70. Now, some of these are really obscure situations that just
  71. *shouldn't* happen with real data and well-written comparison
  72. functions.  But I've found that some of the most time-consuming
  73. sorts are done at the request of the user, and are ones
  74. in which the user can specify several possibly interrelated
  75. keys.  I worried about what would happen if the user managed
  76. to find a combination that would result in something other
  77. than a complete ordering.
  78.  
  79. My comments are interspersed with the results.
  80.  
  81. banzai# test_sort 5000 
  82. HZ = 60
  83. element size = 8
  84. number of elements = 5000
  85.  
  86.  
  87. *** qsort ***
  88. data         compares      stack       heap       user       system
  89. random:         66554        768          0       3.68       0.00
  90. ascend:         57727        960          0       3.00       0.00
  91. descend:        57728        960          0       3.03       0.00
  92. fib asc:        57727        960          0       2.78       0.05
  93. fib desc: ^C
  94. surprise:       61797        864          0       3.75       0.00
  95.  
  96. [This qsort is the one supplied with SunOS 4.1.  It performs well
  97.  under most circumstances but goes into an infinite loop when the 
  98.  comparison always returns 1.  The infinite loop seems to be of
  99.  such a character that the comparison function is being called
  100.  with ever decreasing addresses and so presumably could cause
  101.  segmentation faults under some circumstances.  It's usage of
  102.  stack space and heap space are perfectly fine for modern CPUs.]
  103.  
  104. *** merge_sort ***
  105. data         compares      stack       heap       user       system
  106. random:         55240       1152      40004       2.98       0.02
  107. ascend:         32004       1152      40004       1.92       0.03
  108. descend:        29804       1152      40004       1.72       0.03
  109. fib asc:        32004       1152      40004       1.73       0.00
  110. fib desc:       29804       1152      40004       1.63       0.00
  111. surprise:       44434       1152      40004       2.75       0.00
  112.  
  113. [Based on other tests, the stack space is O(log(n)).  The heap space
  114.  used here is questionable; a more talented programmer might be
  115.  able implement it without using up O(n) space.  A less talented
  116.  programmer would be tempted to place it on the stack, but that's
  117.  a marginal improvement.  In terms of number of comparisons,
  118.  merge_sort's worst case is better than qsort's best case and with
  119.  one exception the same can be said of execution speed.]
  120.  
  121. *** merge_sort(maybe_sorted) ***
  122. data         compares      stack       heap       user       system
  123. random:         56248       1152      40004       3.05       0.10
  124. ascend:          7831       1152      40004       0.48       0.03
  125. descend:        30827       1152      40004       1.77       0.05
  126. fib asc:        33027       1152      40004       1.87       0.02
  127. fib desc:        6023       1152      40004       0.37       0.00
  128. surprise:       34723       1152      40004       2.22       0.00
  129.  
  130. [I modified merge_sort slightly to perform some simple checking to
  131.  see if the array (or subsections of the array) are already in order.  
  132.  It adds about 2% to the number of comparisons in the "normal" case, 
  133.  but for sorting an index which is "almost" sorted already this
  134.  cuts the time down dramatically.]
  135.  
  136. *** quick_sort ***
  137. data         compares      stack       heap       user       system
  138. random:         71409       1536         12       4.82       0.02
  139. ascend:         51822        960         12       2.88       0.00
  140. descend:        54924       1248         12       3.80       0.00
  141. fib asc:     12497500     479808         12     601.07       1.42
  142. fib desc:    12497500          0         12     597.93       1.15
  143. surprise:       57198        672         12       3.97       0.00
  144.  
  145. [The quick sort is adapted from the one found on page 87 of K&R 2; they 
  146.  disclaim it as sub-optimal, for good reason it seems.  I haven't
  147.  had the time to rewrite it though I did fix the infinite loop
  148.  problem, at a marginal cost in speed.  The quadratic behavior
  149.  in the case of a deceptive comparison routine should probably
  150.  not be held against it.]
  151.  
  152. --
  153.  
  154. The actual results are not true for all time and all machines.  The
  155. execution time for these algorithms when using non-brain-damaged
  156. comparison routine are all within a factor of 2.  Sorting a bigger
  157. array brings out the differences more clearly, but at least between
  158. qsort and merge sort the improvement is rather minor.
  159.  
  160. I planned to add a feature for changing the size of the input array
  161. automatically and analyzing the change in time and space usage to
  162. directly calculate O(whatever) for each algorithm, but I'm a bit busy
  163. at the moment.  (Posting to usenet to be precise.)  I'll also be
  164. adding heapsort and shellsort algorithms; if anyone has a qsort-like
  165. drop-in replacement for either or both of those I'd appreciate
  166. a copy.
  167.  
  168.      der krill
  169.  
  170.