home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / TPSORTS.ZIP / SORTS.DOC next >
Encoding:
Text File  |  1986-05-14  |  3.0 KB  |  67 lines
  1.  
  2.  
  3.  
  4.         SORT.COM  is  program  shell designed to allow  comparison  of  a 
  5.         number  of  sorting algorithms.   SORT.PAS is  the  corresponding 
  6.         Turbo  Pascal source file.   The program menu allows the user  to 
  7.         generate  a  desired number of random integers (up to  2000,  but 
  8.         tree  sort  can  handle  only 1600).   The  master  list  can  be 
  9.         presorted if desired,  and display of the numbers can be  toggled 
  10.         on  or  off.   The other menu choices allow the user to test  the 
  11.         particular sorting methods.
  12.  
  13.         The  individual  sorting algorithms appear  as  named  procedures 
  14.         within SORT.PAS.   They were written to gain understanding of the 
  15.         sorts,  and  were  optimized  for clear  expression  rather  than 
  16.         versatility or speed.  
  17.  
  18.         To  compare  the  speed of the various algorithms,  I  timed  the 
  19.         interval  between  my  response to the prompt  "Ready?"  and  the 
  20.         moment  when the sorted list began to print out.   I tested  each 
  21.         sort on 400 and 800 random integers,  and then on the same number 
  22.         sets  after  presorting,  with the following  results  (times  in 
  23.         seconds):
  24.  
  25.         SORT      400       800       400 (PS)  800 (PS)
  26.  
  27.         bubble    29.7      114.8       .3        .3
  28.         count     17.8       70.2     18.0      71.0
  29.         insert    11.5       42.2       .4        .4
  30.         select     9.2       35.6      9.1      35.4
  31.         tree       6.3       14.1      6.3      14.0
  32.         shell      1.9        4.0      1.1       2.1
  33.         heap       1.6        3.5      1.7       3.6
  34.         quick1     1.1        2.1      8.7      failed
  35.         quick2     1.0        2.0       .7       1.2
  36.  
  37.         The  first four sorts are of a class that takes time proportional 
  38.         to n ** 2 to sort n items, shell sort is in an intermediate class 
  39.         that takes time proportional to roughly n ** 1.25,  and the other 
  40.         four are in the best case class that takes time proportional to n 
  41.         log n.  
  42.  
  43.         Note that two of the very simple sorts (bubble and insertion) are 
  44.         excellent  on lists that are already sorted or nearly  so.   Tree 
  45.         sort  is  worse  than shell sort at n this low  because  of  high 
  46.         overhead,  but would eventually catch up at much larger  n.   The 
  47.         simple  quick sort is notoriously bad on presorted lists--at n  = 
  48.         800  it fails due to stack overflow during recursive calls.   The 
  49.         improved  quick  sort  overcomes this problem  and  will  be  the 
  50.         fastest  sort  of  this  collection for  all  but  very  unlikely 
  51.         sequences of numbers.   (In a few rare cases, heap sort will beat 
  52.         it,  since  the  improved quicksort still has a bad  worst  case, 
  53.         while heap sort takes about the same time for best and worse case 
  54.         lists.)
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.                                         1
  62.  
  63.  
  64.  
  65.  
  66.  
  67.