home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c082_122 / 2.ddi / CLIBSRC3.ZIP / QSORT.CAS < prev    next >
Encoding:
Text File  |  1992-06-10  |  11.2 KB  |  359 lines
  1. /*-----------------------------------------------------------------------*
  2.  * filename - qsort.cas
  3.  *
  4.  * function(s)
  5.  *        Exchange  - exchanges two objects
  6.  *        qSortHelp - performs the quicker sort
  7.  *        qsort     - sorts using the quick sort routine
  8.  *-----------------------------------------------------------------------*/
  9.  
  10. /*
  11.  *      C/C++ Run Time Library - Version 5.0
  12.  *
  13.  *      Copyright (c) 1987, 1992 by Borland International
  14.  *      All Rights Reserved.
  15.  *
  16.  */
  17.  
  18.  
  19. #pragma  inline
  20. #include <asmrules.h>
  21. #include <stdlib.h>
  22.  
  23.  
  24. typedef int _CType comparF (const void _FAR *, const void _FAR *);
  25.  
  26. static  comparF    *Fcmp;
  27. static  unsigned    qWidth;
  28.  
  29. /*-----------------------------------------------------------------------*
  30.  
  31. Name            Exchange - exchanges two objects
  32.  
  33. Usage           static  void  near pascal  Exchange (void  *leftP,
  34.                                                      void *rightP);
  35.  
  36. Description     exchanges the qWidth byte wide objects pointed to
  37.                 by leftP and rightP.
  38.  
  39. Return value    Nothing
  40.  
  41. *------------------------------------------------------------------------*/
  42. static  void  near pascal  Exchange (void  *leftP, void *rightP)
  43. {
  44. #if 0
  45.         int  i;
  46.         char  c;
  47.  
  48.         for (i = 0; i < qWidth; i++ ;)
  49.         {
  50.                 c = *((char *) rightP);
  51.                 *((char *) rightP )++ = *((char *) leftP);
  52.                 *((char *) leftP )++ = c;
  53.         }
  54. #endif
  55.  
  56. /*
  57.   Note that in HUGE model DS and ES may differ.
  58. */
  59. #if ! LDATA
  60. asm     push    DS
  61. asm     pop     ES              /* define ES for stos, movs     */
  62. #else
  63. asm     push    DS
  64. #endif
  65.  
  66. asm     cld
  67. asm     mov     cx, qWidth
  68. asm     LES_    di, rightP
  69. asm     LDS_    si, leftP
  70. /*
  71.   Assert: qWidth is never zero, see test at entry to qsort().
  72. */
  73. asm     shr     cx, 1                   /* test for an odd number of bytes */
  74. asm     jnc     xch_wordLoop
  75.  
  76. asm     mov     al, ES_ [di]
  77. asm     movsb                           /* swap bytes, advancing pointers */
  78. asm     mov     [si-1], al
  79. asm     jz      xch_end                 /* if CX was originally 1       */
  80. /*
  81.   Swapping words is almost twice as fast even if running on an 8088 or if
  82.   the data is odd-aligned, since the CPU needs to fetch only half the
  83.   number of instructions per byte.
  84. */
  85. xch_wordLoop:
  86. asm     mov     ax, ES_ [di]
  87. asm     movsw                           /* swap words, advancing pointers */
  88. asm     mov     [si-2], ax
  89. asm     loop    xch_wordLoop
  90.  
  91. xch_end:
  92. #if LDATA
  93. asm     pop     DS
  94. #endif
  95.     return;
  96. }
  97.  
  98. /*-----------------------------------------------------------------------*
  99.  
  100. Background
  101.  
  102. The Quicker Sort algorithm was first described by C.A.R.Hoare in the
  103. Computer Journal, No. 5 (1962), pp.10..15, and in addition is frequently
  104. described in computing literature, notably in D. Knuth's Sorting and
  105. Searching.  The method used here includes a number of refinements:
  106.  
  107. - The median-of-three technique described by Singleton (Communications
  108.   of the A.C.M., No 12 (1969) pp 185..187) is used, where the median
  109.   operation is also the special case sort for 3 elements.  This slightly
  110.   improves the average speed, especially when comparisons are slower
  111.   than exchanges, but more importantly it prevents worst-case behavior
  112.   on partly sorted files.  If a simplistic quicker-sort is run on a file
  113.   which is only slightly disordered (a common need in some applications)
  114.   then it is as slow as a bubble-sort.  The median technique prevents
  115.   this.
  116.  
  117.   Another serious problem with the plain algorithm is that worst-case
  118.   behavior causes very deep recursion (almost one level per table
  119.   element !), so again it is best to use the median technique.
  120.  
  121. - The values of width and compar are copied to static storage and a help
  122.   function with a minimum of parameters is used to reduce the recursion
  123.   overheads.  Recursion is used both for simplicity and because there
  124.   is no practical gain from conversion to loops: the extra housekeeping
  125.   needed for loops needs registers for speed, but the 8086 family has not
  126.   enough registers.  Juggling registers takes just as much time as calling
  127.   subroutines.
  128.  
  129. *------------------------------------------------------------------------*/
  130.  
  131. /*
  132.   Optimize pointer comparisons knowing segments are identical,
  133.   except in HUGE model.
  134. */
  135.  
  136. #if 0                   /* not needed */
  137. #ifdef __HUGE__
  138. #   define  _LT_(x,y)  (x < y)
  139. #else
  140. #   define  _LT_(x,y)  ((unsigned short) x < (unsigned short) y)
  141. #endif
  142. #else
  143. #define _LT_(x,y)       (x < y)
  144. #endif
  145.  
  146. /*-----------------------------------------------------------------------*
  147.  
  148. Name            qSortHelp - performs the quicker sort
  149.  
  150. Usage           static void  near pascal  qSortHelp (char *pivotP,
  151.                                                      size_t nElem);
  152.  
  153. Description     performs the quicker sort on the nElem element array
  154.                 pointed to by pivotP.
  155.  
  156. Return value    Nothing
  157.  
  158. *------------------------------------------------------------------------*/
  159. #pragma warn -sig
  160. #if defined(__HUGE__) || defined(__FARFUNCS__)
  161. #pragma warn -sus
  162. static void  near pascal  qSortHelp (char huge *pivotP, size_t nElem)
  163. #else
  164. static void  near pascal  qSortHelp (char *pivotP, size_t nElem)
  165. #endif
  166. {
  167. #if defined(__HUGE__) || defined(__FARFUNCS__)
  168.     char    huge *leftP, huge *rightP;
  169.     char    huge *pivotEnd, huge *pivotTemp, huge *leftTemp;
  170. #else
  171.     char     *leftP, *rightP, *pivotEnd, *pivotTemp, *leftTemp;
  172. #endif
  173.     unsigned  lNum;
  174.     int       retval;
  175.  
  176.  
  177. tailRecursion:
  178.     if (nElem <= 2)
  179.         {
  180.         if (nElem == 2)
  181.             {
  182.             if (Fcmp (pivotP, rightP = qWidth + pivotP) > 0)
  183.                 Exchange (pivotP, rightP);
  184.             }
  185.         return;
  186.         }
  187.  
  188.     rightP = (nElem - 1) * qWidth + pivotP;
  189.     leftP  = (nElem >> 1) * qWidth + pivotP;
  190.  
  191. /*  sort the pivot, left, and right elements for "median of 3" */
  192.  
  193.     if (Fcmp (leftP, rightP) > 0)
  194.         Exchange (leftP, rightP);
  195.     if (Fcmp (leftP, pivotP) > 0)
  196.         Exchange (leftP, pivotP);
  197.     else if (Fcmp (pivotP, rightP) > 0)
  198.         Exchange (pivotP, rightP);
  199.  
  200.     if (nElem == 3)
  201.         {
  202.         Exchange (pivotP, leftP);
  203.         return;
  204.         }
  205.  
  206. /*  now for the classic Hoare algorithm */
  207.  
  208.     leftP = pivotEnd = pivotP + qWidth;
  209.  
  210.     do
  211.         {
  212.         while ((retval = Fcmp(leftP, pivotP)) <= 0)
  213.             {
  214.             if (retval == 0)
  215.                 {
  216.                 Exchange(leftP, pivotEnd);
  217.                 pivotEnd += qWidth;
  218.                 }
  219.             if (_LT_ (leftP, rightP))
  220.                 leftP += qWidth;
  221.             else
  222.                 goto qBreak;
  223.             }
  224.  
  225.         while (_LT_(leftP, rightP))
  226.             {
  227.             if ((retval = Fcmp(pivotP, rightP)) < 0)
  228.                 rightP -= qWidth;
  229.             else
  230.                 {
  231.                 Exchange (leftP, rightP);
  232.                 if (retval != 0)
  233.                     {
  234.                     leftP += qWidth;
  235.                     rightP -= qWidth;
  236.                     }
  237.                 break;
  238.                 }
  239.             }
  240.         }   while (_LT_(leftP, rightP));
  241.  
  242. qBreak:
  243.  
  244.     if (Fcmp(leftP, pivotP) <= 0)
  245.         leftP = leftP + qWidth;
  246.  
  247.     leftTemp = leftP - qWidth;
  248.  
  249.     pivotTemp = pivotP;
  250.  
  251.     while ((pivotTemp < pivotEnd) && (leftTemp >= pivotEnd))
  252.         {
  253.         Exchange(pivotTemp, leftTemp);
  254.         pivotTemp += qWidth;
  255.         leftTemp -= qWidth;
  256.         }
  257.  
  258.     lNum = (leftP - pivotEnd) / qWidth;
  259.     nElem = ((nElem * qWidth + pivotP) - leftP)/qWidth;
  260.  
  261.     // Sort smaller partition first to reduce stack usage
  262.     if (nElem < lNum)
  263.         {
  264.         qSortHelp (leftP, nElem);
  265.         nElem = lNum;
  266.         }
  267.     else
  268.         {
  269.         qSortHelp (pivotP, lNum);
  270.         pivotP = leftP;
  271.         }
  272.  
  273.     goto tailRecursion;
  274. }
  275. #pragma warn .sig
  276. #if defined(__HUGE__) || defined(__FARFUNCS__)
  277. #pragma warn .sus
  278. #endif
  279.  
  280. /*-----------------------------------------------------------------------*
  281.  
  282. Name            qsort - sorts using the quick sort routine
  283.  
  284. Usage           void qsort(void *base, int nelem, int width, int (*fcmp)());
  285.  
  286. Prototype in    stdlib.h
  287.  
  288. Description     qsort is an implementation of the "median of three"
  289.                 variant of the quicksort algorithm. qsort sorts the entries
  290.                 in a table into order by repeatedly calling the user-defined
  291.                 comparison function pointed to by fcmp.
  292.  
  293.                 base points to the base (0th element) of the table to be sorted.
  294.  
  295.                 nelem is the number of entries in the table.
  296.  
  297.                 width is the size of each entry in the table, in bytes.
  298.  
  299.                 *fcmp, the comparison function, accepts two arguments, elem1
  300.                 and elem2, each a pointer to an entry in the table. The
  301.                 comparison function compares each of the pointed-to items
  302.                 (*elem1 and *elem2), and returns an integer based on the result
  303.                 of the comparison.
  304.  
  305.                         If the items            fcmp returns
  306.  
  307.                         *elem1 <  *elem2         an integer < 0
  308.                         *elem1 == *elem2         0
  309.                         *elem1 >  *elem2         an integer > 0
  310.  
  311.                 In the comparison, the less than symbol (<) means that the left
  312.                 element should appear before the right element in the final,
  313.                 sorted sequence. Similarly, the greater than (>) symbol
  314.                 means that the left element should appear after the right
  315.                 element in the final, sorted sequence.
  316.  
  317. Return value    qsort does not return a value.
  318.  
  319. *------------------------------------------------------------------------*/
  320. #if defined(__FARFUNCS__)
  321. #include <_farfunc.h>
  322. #endif
  323.  
  324. void  _CType _FARFUNC qsort (void _FAR * baseP, size_t nElem, size_t width,
  325.                              comparF *compar)
  326.  
  327. /*
  328.   The table *baseP containing a count of nElem records each of fixed width
  329.   is to be converted from unknown order into ascending order, using the
  330.   ordering provided by the comparison function compar.
  331.  
  332.   The comparison function compar (leftP, rightP) must return less than, equal,
  333.   or greater than zero, according to whether it decides that (record) *leftP
  334.   is less than, equal, or greater than (record) *rightP.
  335.  
  336.   The internal contents of the records are never inspected by qsort.  It
  337.   depends entirely upon compar to decide the format and value of the records.
  338.   This allows the content of the records to be of any fixed length type -
  339.   formatted text, floating point, pointer to variable length record, etc. -
  340.   so long as each record is understood by compar.
  341.  
  342.   The quicker sort algorithm will in general change the relative ordering
  343.   of records which may compare as equal.  For example, if it is attempted
  344.   to use two passes of quick sort on a order file, first by date and then
  345.   by customer name, the result will be that the second sort pass randomly
  346.   jumbles the dates.  It is necessary to design the compar() function to
  347.   consider all the keys and sort in one pass.
  348.  
  349. */
  350.  
  351. {
  352.     if ((qWidth = width) == 0)
  353.         return;
  354.  
  355.     Fcmp = compar;
  356.  
  357.     qSortHelp (baseP, nElem);
  358. }
  359.