home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / alde_c / misc / lib / dlibssrc / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-07-13  |  3.3 KB  |  152 lines
  1. #include <stdio.h>
  2.  
  3. char    *_qbuf = NULL;        /* pointer to storage for qsort() */
  4.  
  5. #define    PIVOT    ((i+j)>>1)
  6.  
  7. static _wqsort(base, lo, hi, cmp)
  8. register int *base;
  9. register int lo;
  10. register int hi;
  11. register int (*cmp)();
  12. {
  13.     int k;
  14.     register int i, j, t;
  15.     register int *p = &k;
  16.  
  17.     while(hi > lo) {
  18.         i = lo;
  19.         j = hi;
  20.         t = PIVOT;
  21.         *p = base[t];
  22.         base[t] = base[i];
  23.         while(i < j) {
  24.             while(((*cmp)((base+j), p)) > 0)
  25.                 --j;
  26.             base[i] = base[j];
  27.             while((i < j) && (((*cmp)((base+i), p)) <= 0))
  28.                 ++i;
  29.             base[j] = base[i];
  30.         }
  31.         base[i] = *p;
  32.         if((i - lo) < (hi - i)) {
  33.             _wqsort(base, lo, (i - 1), cmp);
  34.             lo = i + 1;
  35.         }
  36.         else {
  37.             _wqsort(base, (i + 1), hi, cmp);
  38.             hi = i - 1;
  39.         }
  40.     }
  41. }
  42.  
  43. static _lqsort(base, lo, hi, cmp)
  44. register long *base;
  45. register int lo;
  46. register int hi;
  47. register int (*cmp)();
  48. {
  49.     long k;
  50.     register int i, j, t;
  51.     register long *p = &k;
  52.  
  53.     while(hi > lo) {
  54.         i = lo;
  55.         j = hi;
  56.         t = PIVOT;
  57.         *p = base[t];
  58.         base[t] = base[i];
  59.         while(i < j) {
  60.             while(((*cmp)((base+j), p)) > 0)
  61.                 --j;
  62.             base[i] = base[j];
  63.             while((i < j) && (((*cmp)((base+i), p)) <= 0))
  64.                 ++i;
  65.             base[j] = base[i];
  66.         }
  67.         base[i] = *p;
  68.         if((i - lo) < (hi - i)) {
  69.             _lqsort(base, lo, (i - 1), cmp);
  70.             lo = i + 1;
  71.         }
  72.         else {
  73.             _lqsort(base, (i + 1), hi, cmp);
  74.             hi = i - 1;
  75.         }
  76.     }
  77. }
  78.  
  79. static _nqsort(base, lo, hi, size, cmp)
  80. register char *base;
  81. register int lo;
  82. register int hi;
  83. register int size;
  84. register int (*cmp)();
  85. {
  86.     register int i, j;
  87.     register char *p = _qbuf;
  88.  
  89.     while(hi > lo) {
  90.         i = lo;
  91.         j = hi;
  92.         p = (base+size*PIVOT);
  93.         blkcpy(_qbuf, p, size);
  94.         blkcpy(p, (base+size*i), size);
  95.         p = _qbuf;
  96.         while(i < j) {
  97.             while(((*cmp)((base+size*j), p)) > 0)
  98.                 --j;
  99.             blkcpy((base+size*i), (base+size*j), size);
  100.             while((i < j) && (((*cmp)((base+size*i), p)) <= 0))
  101.                 ++i;
  102.             blkcpy((base+size*j), (base+size*i), size);
  103.         }
  104.         blkcpy((base+size*i), p, size);
  105.         if((i - lo) < (hi - i)) {
  106.             _nqsort(base, lo, (i - 1), size, cmp);
  107.             lo = i + 1;
  108.         }
  109.         else {
  110.             _nqsort(base, (i + 1), hi, size, cmp);
  111.             hi = i - 1;
  112.         }
  113.     }
  114. }
  115.  
  116. qsort(base, num, size, cmp)
  117. char *base;
  118. int num;
  119. int size;
  120. int (*cmp)();
  121. /*
  122.  *    Perform a recursive quick-sort on an array starting at <base>
  123.  *    containing <num> elements of <size> bytes each.  The function
  124.  *    pointed to by <cmp> is used to compare elements.  Pointers to
  125.  *    two items in the array are passed to the function, which must
  126.  *    return a number representing their relationship as follows:
  127.  *        negative    item1 < item2
  128.  *        0        item1 == item2
  129.  *        positive    item1 > item2
  130.  *    The qsort() function requires the use of a temporary data area
  131.  *    that is large enough to hold <size> bytes.  The default space
  132.  *    provided is 128 bytes large.  If your record size is larger than
  133.  *    128 bytes, YOU MUST provide an alternative storage area.  The
  134.  *    global variable "_qbuf" points to the storage qsort() will use.
  135.  *    Setting "_qbuf" to NULL restores use of the internal buffer.
  136.  *    This routine is optimized to avoid N*N sort times for ordered data.
  137.  */
  138. {
  139.     char _qtemp[128];
  140.  
  141.     if(_qbuf == NULL)
  142.         _qbuf = _qtemp;
  143.     if(size == 2)
  144.         _wqsort(base, 0, num-1, cmp);
  145.     else if(size == 4)
  146.         _lqsort(base, 0, num-1, cmp);
  147.     else
  148.         _nqsort(base, 0, num-1, size, cmp);
  149.     if(_qbuf == _qtemp)
  150.         _qbuf = NULL;
  151. }
  152.