home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / PASCAL / SORTKIT1.ZIP / QUICKSRT.PAS < prev    next >
Pascal/Delphi Source File  |  1991-09-08  |  4KB  |  111 lines
  1. (******************************************************************************
  2. *                                  quickSrt                                   *
  3. * perform a generic quick sort in memory, using a generic quicksort object    *
  4. ******************************************************************************)
  5. unit quickSrt;
  6.  
  7.  
  8. {$R-,S-}
  9.  
  10. interface
  11.  
  12. type
  13.    arrayOfPointersPtr = ^ arrayOfPointers;
  14.    arrayOfPointers = array [1..1] of pointer;
  15.  
  16.    quickSortPtr = ^ quickSort;
  17.    quickSort = object
  18.       numberOfElements  : longInt;
  19.       ptrArray          : arrayOfPointersPtr;
  20.       blokSize          : word;
  21.  
  22.       constructor init  (  noe           : longint;
  23.                            pa            : arrayOfPointersPtr;
  24.                            bs            : word
  25.                         );
  26.       function compare(a, b : pointer) : byte ; virtual;  { 0 if a = b,
  27.                                                             1 if a > b,
  28.                                                             2 if a < b }
  29.       procedure doYourJob;
  30.       procedure recursiveSort(left, right : longInt);
  31.  
  32.    end; { quickSort object definition }
  33.  
  34. implementation
  35.  
  36. (******************************************************************************
  37. *                               quickSort.init                                *
  38. ******************************************************************************)
  39. constructor quickSort.init;
  40. begin
  41.   numberOfElements := noe;
  42.   ptrArray         := pa; { pointer to an array of pointers to the data }
  43.   blokSize         := bs;
  44. end; {quickSort.init}
  45.  
  46. (******************************************************************************
  47. *                              quickSort.compare                              *
  48. ******************************************************************************)
  49. function quickSort.compare;
  50. begin
  51.    { descendent will override ... }
  52. end; {quickSort.compare}
  53.  
  54. (******************************************************************************
  55. *                           quickSort.recursiveSort                           *
  56. * here is the main body of the alogorithm. we use the middle record as the    *
  57. * pivot                                                                       *
  58. ******************************************************************************)
  59. procedure quickSort.recursiveSort;
  60. var
  61.   i,j,x: longInt;
  62.   y,p  : Pointer;
  63.   mid  : pointer; { here is the data we are interested in copied to .. }
  64. begin
  65.   i := left; 
  66.   j := right; 
  67.   getMem(mid, blokSize);
  68.   x := (left + right) div 2;
  69.   move(ptrArray^[x]^, mid^, blokSize); { we will compare to mid^ }
  70.   repeat
  71.   {$R-}
  72.     while (compare(mid, ptrArray^[i]) = 1) do { when p[x] > p[i] }
  73.       inc(i);
  74.     while (compare(ptrArray^[j], mid) = 1) do { when p[j] > p[x] }
  75.       dec(j);
  76.     if (i <= j) then begin
  77.       y := ptrArray^[i]; 
  78.       ptrArray^[i] := ptrArray^[j]; 
  79.       ptrArray^[j] := y;
  80.       inc(i);
  81.       dec(j);
  82.     end; { do the swap }
  83.   until (i > j);
  84.   freemem(mid, blokSize);
  85.   if ((j - left) < (right - i)) then begin { left partition is smaller then right }
  86.    if (left < j) then
  87.       recursiveSort(left, j);
  88.    if (i < right) then
  89.       recursiveSort(i, right);
  90.   end else begin { right partition is smaller }
  91.    if (i < right) then
  92.       recursiveSort(i, right);
  93.    if (left < j) then 
  94.       recursiveSort(left, j);
  95.   end; 
  96. end; {quickSort.recursiveSort}
  97.  
  98. (******************************************************************************
  99. *                             quickSort.doYourJob                             *
  100. ******************************************************************************)
  101. procedure quickSort.doYourJob;
  102. begin
  103.    recursiveSort( 1, numberOfElements);
  104. end; {quickSort.doYourJob}
  105.  
  106. (******************************************************************************
  107. *                                    MAIN                                     *
  108. ******************************************************************************)
  109. end.
  110. 
  111.