home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / mbug / mbug117.arc / SORTS.LBR / SORTS.DQC / SORTS.DOC
Text File  |  1979-12-31  |  3KB  |  57 lines
  1. SORT.CO═áá i≤áá prograφá shel∞á designeΣá t∩áá allo≈ ì
  2. comparisoεá oµá ßá numbe≥á oµá sortinτáá algorithms«  ì
  3. SORT.PA╙á i≤á thσ correspondinτ Turb∩ Pasca∞á sourcσ ì
  4. file«á  Thσ prograφ men⌡ allow≤ thσ use≥ t∩ generatσ ì
  5. ß desireΣ numbe≥ oµ randoφ integer≤ (u≡ t∩ 2000¼ bu⌠ ì
  6. treσá sor⌠ caε handlσ onl∙ 1600)«á  Thσ maste≥á lis⌠ ì
  7. caεá bσá presorteΣ iµ desired¼á anΣ displa∙á oµá thσ ì
  8. number≤á caε bσ toggleΣ oε o≥ off«á  Thσ othe≥á men⌡ ì
  9. choice≤á allo≈á thσá use≥á t∩á tes⌠á thσá particula≥ ì
  10. sorting methods.
  11.  
  12. Thσá individua∞á sortinτ algorithm≤ appea≥ a≤á nameΣ ì
  13. procedure≤á withiε SORT.PAS«á  The∙ werσ writteεá t∩ ì
  14. gaiε understandinτ oµ thσ sorts¼á anΣ werσ optimizeΣ ì
  15. fo≥á clea≥á expressioε rathe≥á thaεá versatilit∙á o≥ ì
  16. speed«á  
  17.  
  18. T∩á comparσ thσ speeΣ oµ thσ variou≤á algorithms¼á ╔ ì
  19. timeΣ thσ interva∞ betweeε m∙ responsσ t∩ thσ promp⌠ ì
  20. "Ready?óá anΣ thσ momen⌠ wheε thσ sorteΣ lis⌠á begaε ì
  21. t∩á prin⌠á out«á  ╔ testeΣ eacΦ sor⌠ oε 40░ anΣá 80░ ì
  22. randoφá integers¼á anΣ theε oε thσ samσ numbe≥á set≤ ì
  23. afte≥ presorting¼á witΦ thσ followinτ result≤ (time≤ ì
  24. in seconds):
  25.  
  26. SORT      400       800       400 (PS)  800 (PS)
  27.  
  28. bubble    29.7      114.8       .3        .3
  29. count     17.8       70.2     18.0      71.0
  30. insert    11.5       42.2       .4        .4
  31. select     9.2       35.6      9.1      35.4
  32. tree       6.3       14.1      6.3      14.0
  33. shell      1.9        4.0      1.1       2.1
  34. heap       1.6        3.5      1.7       3.6
  35. quick1     1.1        2.1      8.7      failed
  36. quick2     1.0        2.0       .7       1.2
  37.  
  38. Thσ firs⌠ fou≥ sort≤ arσ oµ ß clas≤ tha⌠ take≤á timσ ì
  39. proportiona∞á t∩ ε *¬ ▓ t∩ sor⌠ ε items¼á shel∞ sor⌠ ì
  40. i≤áá iεá aεá intermediatσá clas≤á tha⌠á take≤áá timσ ì
  41. proportiona∞á t∩ roughl∙ ε *¬ 1.25¼á anΣá thσá othe≥ ì
  42. fou≥á arσá iεá thσ bes⌠ casσ clas≤ tha⌠á take≤á timσ ì
  43. proportiona∞ t∩ ε loτ n«á  
  44.  
  45. Notσá tha⌠ tw∩ oµ thσ ver∙ simplσ sort≤ (bubblσá anΣ ì
  46. insertion⌐á arσ excellen⌠ oε list≤ tha⌠ arσá alread∙ ì
  47. sorteΣ o≥ nearl∙ so«á  Treσ sor⌠ i≤ worsσ thaε shel∞ ì
  48. sor⌠á a⌠á ε thi≤ lo≈ becausσ oµ higΦá overhead¼á bu⌠ ì
  49. woulΣá eventuall∙ catcΦ u≡ a⌠ mucΦá large≥á n«á  Thσ ì
  50. simplσá quicδá sor⌠ i≤ notoriousl∙ baΣ oεá presorteΣ ì
  51. lists--a⌠á εá ╜ 80░ i⌠ fail≤ duσ t∩á stacδá overflo≈ ì
  52. durinτá recursivσ calls«á  Thσ improveΣá quicδá sor⌠ ì
  53. overcome≤á thi≤ probleφ anΣ wil∞ bσ thσ fastes⌠ sor⌠ ì
  54. oµá thi≤á collectioεá fo≥á al∞á bu⌠á ver∙áá unlikel∙ ì
  55. sequence≤á oµ numbers«á  (Iε ß fe≈ rarσ cases¼á hea≡ ìèsor⌠á wil∞á bea⌠ it¼á sincσ thσá improveΣá quicksor⌠ ì
  56. stil∞á ha≤ ß baΣ wors⌠ case¼á whilσ hea≡ sor⌠á take≤ ì
  57. about the same time for best and worse case lists.)