home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sources / misc / 4213 / README < prev    next >
Encoding:
Text File  |  1992-12-18  |  7.8 KB  |  173 lines
  1.  
  2. VERSION
  3.  
  4.     This is version 0 of the the Sort Flogger.
  5.  
  6. OVERVIEW
  7.  
  8.     This is a small collection of some of the more popular sort
  9. algorithms, including:
  10.  
  11.       bubble sort -- any 1st semester course in CS
  12.       heap sort -- contributed by der Mouse
  13.       insertion sort -- any 1st semester course in CS
  14.       merge sort -- roughly patterned after Knuth Vol. 3
  15.       quick sort -- C.A.R. Hoare's as given in K&R 2 pg 87
  16.       shell sort -- D.L. Shell as given in K&R 2 pg 62
  17.       bogo sort -- worst-case sort by Richard Krehbiel
  18.  
  19.     A slightly weird test routine is provided which calculates some
  20. performance measurements on the above algorithms and also on the
  21. qsort() function provided with your system, as well as verifying that
  22. the sort actually worked and that it didn't modify anything immediately
  23. above or below the array, that it doesn't leak memory, and whether
  24. or not it's stable.  These tests are carried out in a variety of
  25. situations designed to highlight worst-case behavior.
  26.  
  27.     These implementations of the sort functions are all compatible with
  28. qsort()'s parameter list, so if you think your application spends too
  29. much time sorting, you can just s/qsort/merge_sort/ and link in the
  30. sort library and give it a try.  If you think it doesn't spend *enough*
  31. time sorting, try bubble_sort instead.
  32.  
  33.     The merge sort declares a global int called _maybe_sorted which
  34. tells merge sort that the data in the array may already be mostly in
  35. order.  It is advisory--the algorithm will produce the correct results
  36. regardless of _maybe_sorted's value; however the execution time for
  37. merge_sort will be quite a bit less if this is set and the array is
  38. already mostly sorted.  If the array isn't sorted at all, this option
  39. extracts about 2% speed penalty.
  40.  
  41.     The heapsort was contributed by mouse@larry.mcrcim.mcgill.edu
  42. aka "der Mouse".
  43.  
  44.     The merge_sort() function is the only one I've taken any trouble to
  45. optimize.
  46.  
  47. INSTALLATION
  48.  
  49.     See the INSTALLATION document which should be nearby.
  50.  
  51. USAGE
  52.  
  53.     Just type "flogger" or "flogger <number>" and watch what happens.
  54.  
  55. DESCRIPTION OF OUTPUT
  56.  
  57.     It seems like it doesn't really do anything but spit out numbers,
  58. and rather slowly at that.  The version and patch level of the program
  59. is printed; the resolution of the clock is printed; the size of the
  60. elements is reported; and the number of elements to be sorted is
  61. reported.
  62.  
  63.     For each sort algorithm, a table of measurements is reported.  The
  64. rows describe the situation the sort algorithm was presented with for
  65. those measurements and the columns represent the type of measurement
  66. taken.  The rows (situations) are:
  67.  
  68.     random:   The contents of the array to be sorted are pseudo 
  69.               random numbers generated by rand(), with two special
  70.               values excluded for the purpose of detecting overwrites
  71.               at the ends of the array.
  72.     ascend:   The array is already completely in order.  To simply
  73.               verify this fact is all that's required of the sort
  74.               algorithm; ironically, bubble sort outperforms all
  75.               the rest in this case.
  76.     descend:  The array is exactly in reverse order.  Theoretically,
  77.               an sort function could detect this and swap ends in
  78.               linear time, but it hardly seems useful.
  79.     fib asc:  The contents of the array are irrelevant; the comparison
  80.               function passed to the routine always says that its
  81.               first argument is less than its second.
  82.     fib desc: Similarly, the comparison function always says that its
  83.               first argument is greater than its second.
  84.     surprise: A pseudorandom result is returned from the comparison 
  85.               function in an attempt to confound the algorithms' efforts
  86.               at sorting.
  87.     mostly:   Similar to ascend, but the first and last elements
  88.               are reversed.  This is meant to simulate an index which
  89.               is pretty much already sorted and only a small number
  90.               of new items need to be inserted.
  91.     equiv:    The comparison function reports that all elements 
  92.               compare equal.  The data is arranged so that a
  93.               check can be made for whether the algorithm is
  94.               stable; that is the property that records with
  95.               equal keys stay in the same relative order in the
  96.               array that they were in before the sort began.
  97.  
  98. The columns refer to these measurements:
  99.  
  100.     compares: The number of calls to the comparison routine during
  101.               the sort.  I consider this very important, as most
  102.               of the sorting bottlenecks I've experience center
  103.               around the comparison function.
  104.     stack:    (Estimated) Some semi-non-portable attempts to record
  105.               the growth of the stack are made and a number comes
  106.               out.  I consider O(log n) use of the stack acceptable
  107.               on modern machines and none of these algorithms are
  108.               worse than that. 
  109.     heap:     Amount of malloc'd storage as reported by mallinfo().
  110.               If your C library doesn't support mallinfo(), the
  111.               compiler will probably barf on flogger.c.  The flogger
  112.               checks for memory leaks.
  113.     user:     Amount of user mode CPU time as reported by times().
  114.               This includes time for both the operation of the
  115.               sort function and the comparison function; as these
  116.               are only marginally related, this number is not
  117.               useful for estimating how long it might take to 
  118.               sort useful data in some other program.
  119.     system:   Amount of system CPU time as reported by times().
  120.               Generally 0.00 or very small.  If a sort algorithm
  121.               uses lots of system time it's probably a Trojan horse
  122.               trying to break into the passwd file or delete your
  123.               home directory or something so maybe you should
  124.               start shuffling through your desk looking for a recent
  125.               backup tape.  I may remove this in a future version
  126.               (the report of system time, not the Trojan horse)
  127.               in favor of another metric, perhaps wall clock time.
  128.  
  129.     But it isn't enough simply to be fast, a sort algorithm also has
  130. to be correct.  To that end, the flogger routine verifies that
  131. the array was actually sorted, at least when the comparison routine
  132. wasn't lying.  It also checks that magic values in the memory locations
  133. immediately above and below the array were not accidentally accessed
  134. or overwritten.
  135.  
  136.     The bogo sort run is skipped if n is sufficiently large that
  137. it's execution would run into trillions of cycles (approx n = 15).
  138.  
  139. MISCELLANEOUS
  140.  
  141.     When running the test routine, some sorts take so long that you
  142. might lose patience.  Keyboard interrupt (aka Control-C) will abort the
  143. current sort test and move on to the next.  If you really want the
  144. program to end, give it a quit signal (Control-\) or send it a signal
  145. with the kill command.   You can also background it (Control-Z) from
  146. the C-shell then kill it.
  147.  
  148.     The size of the elements being sorted is hard-coded at the moment,
  149. but it can be changed by going into flogger.c and changing the typedefs for
  150.  
  151.     #define TEST_TYPE double
  152.     #define TEST_FUNC double_compare
  153.  
  154. into
  155.  
  156.     #define TEST_TYPE int
  157.     #define TEST_FUNC int_compare
  158.  
  159. or back again.  Or add a new type and a new comparison function.
  160.  
  161.     Several of the sort algorithms are not re-entrant which means
  162. you shouldn't call the sort from within the very same comparison 
  163. function you passed into that sort in the first place.
  164.  
  165. COPYRIGHT
  166.  
  167.     Since none of the sort algorithms are mine and anyone with a copy
  168. of Knuth Vol 3 and a little knowledge of C could type them in as easily
  169. as I did, there isn't much point in claiming a copyright, much less
  170. applying for a patent.  I wanted to disclaim liability though, so I put
  171. a few minor restrictions on the code, as set forth in each of the
  172. source files.
  173.