home *** CD-ROM | disk | FTP | other *** search
/ Big Blue Disk 17 / bbd17.zip / SORTDEMO.TXT < prev    next >
Text File  |  1987-12-03  |  4KB  |  83 lines
  1. |D╔═══════════╗═══════════════════════════════════════════════════════════════════
  2. |D║ |5Brainware |D║═══════════════════════════════════════════════════════════════════
  3. |D╚═══════════╝═══════════════════════════════════════════════════════════════════
  4.  
  5. ^C^1A Pair of Sorts
  6. ^Cby
  7. ^CJohn Sigle
  8.  
  9.    This section includes animated demonstrations of two sorting methods: 
  10. InsertionSort and ShellSort.  Each demo shows a PASCAL program as it executes 
  11. as well as showing the data values being manipulated.  These demos can be run 
  12. at varying speeds or in single step mode (a line is executed when you press 
  13. the spacebar.)  They vividly show the nature of the sorting method and relate 
  14. it directly to a PASCAL program for performing the sort. 
  15.  
  16.    There are over a dozen truly distinct sorting methods; to name a few: 
  17. InsertionSort, SelectionSort, BubbleSort, ShellSort, QuickSort, HeapSort, 
  18. MergeSort and RadixSort.  To further complicate matters, each of these has a 
  19. handful of significant variations.  So what?  Well, these methods differ 
  20. significantly in their inherent efficiency.  It doesn't matter which method 
  21. you use if you are only sorting 40 or 50 items.  However, if you have 10,000 
  22. items or so to sort, your choice of method can literally mean the difference 
  23. between 1 minute and 1 day of time required to accomplish the sort. 
  24.  
  25.    InsertionSort is one of the simpler methods.  As with most of the simpler 
  26. methods, its inherent efficiency is relatively poor. ShellSort, which is a 
  27. cousin of InsertionSort, is slightly more complicated but has substantially 
  28. better inherent efficiency. 
  29.  
  30.    InsertionSort works as follows.  It consists of a number of stages. Actually 
  31. the number of stages is one less than the number of items to be sorted.  At 
  32. the start of each stage a beginning portion of the list to be sorted, in 
  33. ascending order say, has already been put in order. During the stage the first 
  34. item beyond this beginning portion is moved back within the beginning portion 
  35. to the position where it belongs, thereby increasing the size of this (sorted) 
  36. beginning portion. 
  37.  
  38.    Try the InsertionSort demo to see how it works.  You can control the speed 
  39. by pressing a digit 0-9 (not the numeric keypad) at any time.  Nine is the 
  40. highest speed while 1 is the lowest.  A speed of 0 puts you in single-step 
  41. mode. In that mode you press the spacebar twice to execute a line of the 
  42. program.  At any time you can scroll the program display forward or backward 
  43. by means of the up or down arrows.  At the conclusion of the demo the number 
  44. of comparisons, swaps and assignments performed is reported. 
  45.  
  46.    ShellSort, invented by D. L. Shell, is only a few lines longer than 
  47. InsertionSort and is very strongly related to it.  It involves the use of 
  48. InsertionSort several times on various parts of the list to be sorted. 
  49. ShellSort proceeds in several phases. For each phase there is an associated 
  50. distance value.  This distance value is reduced with each successive phase, 
  51. with the last phase having a distance value of 1. During each phase of 
  52. ShellSort, InsertionSort is used a number of times to sort a portion of the 
  53. list.  The trick is that each portion does not consist of consecutive items of 
  54. the list but rather of items separated by the distance value associated with 
  55. the phase.  Since the last phase uses a distance of 1 it is exactly an 
  56. InsertionSort of the entire list.  However, by the time this last phase occurs 
  57. the items are almost in order and relatively few comparisons and swaps are 
  58. required. 
  59.  
  60.    The secret of ShellSort's efficiency is the fact that an item can make a 
  61. large move toward the position where it belongs on the basis of a single 
  62. comparison.  This is true of all the more efficient sorting methods.  It is 
  63. not true for InsertionSort where an item can only move one position on the 
  64. basis of one comparison. 
  65.  
  66.    Try the ShellSort demo to see ShellSort in action.
  67.  
  68.    Both of these demos can be accessed by selecting "Run It" for this item, 
  69. and picking which one to run when asked.  The source code, in Turbo Pascal, 
  70. for the sorting algorithms of each is in the files INSERT.PAS and SHELL.PAS 
  71. respectively.
  72.  
  73.    To run this program outside BIG BLUE DISK, type ^1PASRUN SORTDEMO^0. 
  74.  
  75. DISK FILES THIS PROGRAM USES:
  76. ^FSORTDEMO.CHN
  77. ^FINSERTC.CHN
  78. ^FSHELLC.CHN
  79. ^FPASRUN.COM
  80. ^FRETURN.CHN
  81. ^FINSERT.PAS
  82. ^FSHELL.PAS
  83.