home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / DLIBSSRC.ZIP / HSORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-07-14  |  3.3 KB  |  171 lines
  1. /*
  2.  *    Heap sorting functions
  3.  */
  4.  
  5. static _wsift(base, i, n, cmp)
  6. register int *base;
  7. register int i;
  8. register int n;
  9. register int (*cmp)();
  10. {
  11.     register int j, t;
  12.  
  13.     while((j = ((i << 1) + 1)) < n) {
  14.         if((j < (n - 1)) && ((*cmp)((base+j), (base+j+1)) < 0))
  15.             ++j;
  16.         if((cmp)((base+i), (base+j)) < 0) {
  17.             t = base[i];
  18.             base[i] = base[j];
  19.             base[j] = t;
  20.             i = j;
  21.         }
  22.         else
  23.             break;
  24.     }
  25. }
  26.  
  27. static _whsort(base, num, cmp)
  28. register int *base;
  29. register int num;
  30. register int (*cmp)();
  31. {
  32.     register int i, j;
  33.  
  34.     for(i = ((num >> 1) - 1); (i > 0); --i)
  35.         _wsift(base, i, num, cmp);
  36.     i = num;
  37.     while(i > 1) {
  38.         _wsift(base, 0, i--, cmp);
  39.         j = *base;
  40.         *base = *(base + i);
  41.         *(base + i) = j;
  42.     }
  43. }
  44.  
  45. static _lsift(base, i, n, cmp)
  46. register long *base;
  47. register int i;
  48. register int n;
  49. register int (*cmp)();
  50. {
  51.     register int j;
  52.     register long t;
  53.  
  54.     while((j = ((i << 1) + 1)) < n) {
  55.         if((j < (n - 1)) && ((*cmp)((base+j), (base+j+1)) < 0))
  56.             ++j;
  57.         if((cmp)((base+i), (base+j)) < 0) {
  58.             t = base[i];
  59.             base[i] = base[j];
  60.             base[j] = t;
  61.             i = j;
  62.         }
  63.         else
  64.             break;
  65.     }
  66. }
  67.  
  68. static _lhsort(base, num, cmp)
  69. register long *base;
  70. register int num;
  71. register int (*cmp)();
  72. {
  73.     register int i;
  74.     register long j;
  75.  
  76.     for(i = ((num >> 1) - 1); (i > 0); --i)
  77.         _lsift(base, i, num, cmp);
  78.     i = num;
  79.     while(i > 1) {
  80.         _lsift(base, 0, i--, cmp);
  81.         j = *base;
  82.         *base = *(base + i);
  83.         *(base + i) = j;
  84.     }
  85. }
  86.  
  87. static _nswap(pa, pb, n)
  88. register char *pa;
  89. register char *pb;
  90. register int n;
  91. {
  92.     register char c;
  93.  
  94.     while(n--) {
  95.         c = *pa;
  96.         *pa++ = *pb;
  97.         *pb++ = c;
  98.     }
  99. }
  100.  
  101. static _nsift(base, i, n, size, cmp)
  102. register char *base;
  103. register int i;
  104. register int n;
  105. register int size;
  106. register int (*cmp)();
  107. {
  108.     register int j;
  109.     register char *p;
  110.  
  111.     while((j = ((i << 1) + 1)) < n) {
  112.         p = (base+size*j);
  113.         if((j < (n - 1)) && ((*cmp)(p, p+size) < 0)) {
  114.             ++j;
  115.             p += size;
  116.         }
  117.         if((cmp)((base+size*i), p) < 0) {
  118.             _nswap((base+size*i), p, size);
  119.             i = j;
  120.         }
  121.         else
  122.             break;
  123.     }
  124. }
  125.  
  126. static _nhsort(base, num, size, cmp)
  127. register char *base;
  128. register int num;
  129. register int size;
  130. register int (*cmp)();
  131. {
  132.     register int i, j;
  133.  
  134.     for(i = ((num >> 1) - 1); (i > 0); --i)
  135.         _nsift(base, i, num, size, cmp);
  136.     i = num;
  137.     while(i > 1) {
  138.         _nsift(base, 0, i--, size, cmp);
  139.         _nswap(base, (base+size*i), size);
  140.     }
  141. }
  142.  
  143. hsort(base, num, size, cmp)
  144. char *base;
  145. int num;
  146. int size;
  147. int (*cmp)();
  148. /*
  149.  *    Perform an N*log(N) heap-sort on an array starting at <base>
  150.  *    containing <num> elements of <size> bytes each.  The function
  151.  *    pointed to by <cmp> is used to compare elements.  Pointers to
  152.  *    two items in the array are passed to the function, which must
  153.  *    return a number representing their relationship as follows:
  154.  *        negative    item1 < item2
  155.  *        0        item1 == item2
  156.  *        positive    item1 > item2
  157.  *    The hsort() function requires no extra storage, is not recursive,
  158.  *    and has an almost constant N*log(N) sort time.  In the average
  159.  *    case, it is about half as fast as qsort() on random data.  If
  160.  *    portability is a concern, it should be noted that qsort() is
  161.  *    almost always available, but hsort() is not.
  162.  */
  163. {
  164.     if(size == 2)
  165.         _whsort(base, num, cmp);
  166.     else if(size == 4)
  167.         _lhsort(base, num, cmp);
  168.     else
  169.         _nhsort(base, num, size, cmp);
  170. }
  171.