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