home *** CD-ROM | disk | FTP | other *** search
/ Big Blue Disk 19 / bbd19.zip / QUICK1.TXT < prev    next >
Text File  |  1988-03-03  |  5KB  |  90 lines
  1. |D╔═══════════╗═══════════════════════════════════════════════════════════════════
  2. |D║ |5Brainware |D║═══════════════════════════════════════════════════════════════════
  3. |D╚═══════════╝═══════════════════════════════════════════════════════════════════
  4.  
  5. ^C^1QuickSort Demo
  6. ^Cby
  7. ^CJohn Sigle
  8.  
  9. ^CThe Quickest Sort
  10.  
  11.    No single sorting method is universally best.  All algorithms have some 
  12. kinds of data on which they perform poorly.  However, the Quicksort algorithm, 
  13. created by C. A. R. Hoare, is considered to be the fastest general sorting 
  14. method. 
  15.  
  16.    Quicksort is a good example of a recursive program.  A recursive program is 
  17. one which calls itself.  If this seems circular, it is - in part.  In English 
  18. we are taught not to define an entity in terms of itself.  Well, in 
  19. programming it is acceptable (even elegant) to define a program partly in 
  20. terms of itself, provided that there is an escape hatch, a part of the 
  21. definition which is not recursive, which will eventually be applied to produce 
  22. a specific result.
  23.  
  24.    A problem is a good candidate for a recursive solution if it can be broken 
  25. down into subproblems and if some of these subproblems are of the exact same 
  26. nature as the original problem but smaller in size.  This is the strategy of 
  27. the Quicksort algorithm.
  28.  
  29.    Quicksort begins by selecting a value from the list to be sorted. This value 
  30. will be called the "pivot" value.  It is not critical how this value is 
  31. selected.  One approach is to select the item in the middle of the list.  The 
  32. list will then be rearranged so that those values which are less than or equal 
  33. to the pivot value are moved to one end of the list (the left end) and those 
  34. values which are greater than or equal to the pivot are moved to the other 
  35. end.  This is called partitioning the list into 2 partitions.  (Actually, 
  36. depending on the data values involved, there may be a third partition in the 
  37. middle consisting of value(s) equal to the pivot.  If this third partition 
  38. develops, its value(s) are in their final resting place and do not move during 
  39. the rest of the sorting process.)
  40.  
  41.    At this point we have made some progress.  All we need to do is sort each of 
  42. the 2 partitions developed above.  What method shall we use????  You guessed 
  43. it!!!!   Quicksort!!!!   Recursion!!!!
  44.  
  45.    What is the escape hatch?  It occurs when we get down to a partition so 
  46. small that it contains only one value.  We simply quit, since a partition of 
  47. one value is "sorted".
  48.  
  49.    The partitioning method is interesting and is what gives Quicksort its 
  50. superior performance.  A scan is made from the beginning of the list forward, 
  51. looking for a value that belongs in the other end, that is, a value which is 
  52. greater than or equal to the pivot value.  When this is located a scan is made 
  53. from the end of the list backward, looking for a value that belongs in the 
  54. other end, that is, a value which is less than or equal to the pivot value.  
  55. When this is located a swap is made of the two values located.  The scans are 
  56. resumed from these locations and the process continues until the scans meet 
  57. and cross.
  58.  
  59.    The secret of Quicksort's efficiency is that values can make large jumps 
  60. toward their final positions as a result of very few comparisons.
  61.  
  62.    This disk contains sample Turbo Pascal code for a version of Quicksort 
  63. (QUICK1.PAS) as well as an animated demonstration (QUICK1-D.CHN) of this 
  64. program. This demo shows the PASCAL program as it executes as well as the data 
  65. values being manipulated.  The demo can be run at varying speeds. It vividly 
  66. shows the nature of this sorting method and relates it directly to a PASCAL 
  67. program for performing the sort. 
  68.  
  69.    Try the demo QUICK1-D to see how it works.  You can control the speed by 
  70. pressing a digit 0-9 (not the numeric keypad) at any time.  Nine is the 
  71. highest speed while 1 is the lowest.  A speed of 0 puts you in single-step 
  72. mode. In that mode you press the spacebar twice to execute a line of the 
  73. program.  You can scroll the program display forward or backward at any time 
  74. by means of the up or down arrows.  At the conclusion of the demo the total 
  75. number of comparisons, swaps and assignments performed is reported.
  76.  
  77.    The advantage of Quicksort over other methods is not very dramatic with only 
  78. 20 values to sort.  If 1000 values are to be sorted the advantage is amazing.  
  79. The explanation for this is that there is some fixed overhead work associated 
  80. with each partitioning.  It takes large partitions for Quicksort to really get 
  81. cranked up and show its stuff.
  82.  
  83.    This leads to one of the many variations of Quicksort which have been 
  84. suggested.  It involves using a different (simpler) method, such as Insertion 
  85. sort, to sort partitions which are smaller than some fixed size, say 10.
  86.  
  87. Happy sorting!!!!
  88.  
  89.    To run this program outside the BIG BLUE DISK menu, type ^1PASRUN QUICK1-D^0.
  90.