home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 316 / libsrc / nsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-20  |  3.4 KB  |  178 lines
  1.  
  2. /* jrd...
  3.  * I found this sorter lying around on one of the MIT machines.
  4.  * It had no commentary or docs that I could find, I've added some.
  5.  * It seems to work, but I'm not sure whether to trust it.
  6.  * I guess if the price is right I shouldn't complain...
  7.  */
  8.  
  9. #define    T1    4            /* chunk size? */
  10. #define    T2    6
  11.  
  12. /* I don't know why these are globals, not parameters... */
  13.  
  14. static  int    (*compare_elts)();
  15. static  int    nbytes_elt;
  16. static  int    seg_size;
  17. static  int    seg_mid;
  18.  
  19. /* this entry pt added y jrd */
  20.  
  21. qsort (vect, n_elts, elt_size, compare_fun)
  22. char * vect;
  23. int n_elts, elt_size;
  24. int (* compare_fun)();
  25. {
  26.   nsort(vect, n_elts, elt_size, compare_fun);
  27. }
  28.  
  29.  
  30. nsort(vect, n_elts, elt_size, compare_fun)
  31. char    *vect;            /* the vector to be sorted */
  32. int    n_elts;            /* n frobs */
  33. int    elt_size;        /* size in bytes of a frob */
  34. int    (* compare_fun)();    /* fun to compare two frobs */
  35. {
  36.   register char c, *i, *j, *elt_1, *elt_2;
  37.   char *low_lim, *high_lim;
  38.  
  39.   if (n_elts <= 1)
  40.     return;
  41.   nbytes_elt = elt_size;
  42.   compare_elts = compare_fun;
  43.   seg_size = nbytes_elt * T1;
  44.   seg_mid = nbytes_elt * T2;
  45.   high_lim = vect + n_elts * nbytes_elt;
  46.   if (n_elts >= T1) 
  47.     {
  48.     sort_chunk(vect, high_lim);
  49.     elt_2 = vect + seg_size;
  50.     }
  51.     else
  52.     {
  53.     elt_2 = high_lim;
  54.     }
  55.  
  56.   for (j = elt_1 = vect; (elt_1 += nbytes_elt) < elt_2; )
  57.     if (compare_elts(j, elt_1) > 0)
  58.         j = elt_1;
  59.   if (j != vect)
  60.     {
  61.     /* swap j into place */
  62.     for (i = vect, elt_2 = vect + nbytes_elt; i < elt_2; ) 
  63.         {
  64.         c = *j;
  65.         *j++ = *i;
  66.         *i++ = c;
  67.         }
  68.     }
  69.  
  70.   for (low_lim = vect; (elt_2 = low_lim += nbytes_elt) < high_lim; ) 
  71.     {
  72.     while (compare_elts(elt_2 -= nbytes_elt, low_lim) > 0)
  73.         /* void */;
  74.     if ((elt_2 += nbytes_elt) != low_lim) 
  75.         {
  76.         for (elt_1 = low_lim + nbytes_elt; --elt_1 >= low_lim; ) 
  77.             {
  78.             c = *elt_1;
  79.             for (i = j = elt_1; (j -= nbytes_elt) >= elt_2; i = j)
  80.                 *i = *j;
  81.             *i = c;
  82.             }
  83.         }
  84.     }
  85. }
  86.  
  87. static sort_chunk(vect, high_lim)
  88. char *vect, *high_lim;
  89. {
  90.   register char c, *i, *j, *jj;
  91.   register int ii;
  92.   char *mid, *tmp;
  93.   int lo, hi;
  94.  
  95.   lo = high_lim - vect;
  96.   do
  97.     {
  98.     mid = i = vect + nbytes_elt * ((lo / nbytes_elt) >> 1);
  99.     if (lo >= seg_mid) 
  100.         {
  101.         j = (compare_elts((jj = vect), i) > 0 ? jj : i);
  102.         if (compare_elts(j, (tmp = high_lim - nbytes_elt)) > 0) 
  103.             {
  104.             j = (j == jj ? i : jj);
  105.             if (compare_elts(j, tmp) < 0)
  106.                 j = tmp;
  107.             }
  108.         if (j != i) 
  109.             {
  110.             ii = nbytes_elt;
  111.             do
  112.                 {
  113.                 c = *i;
  114.                 *i++ = *j;
  115.                 *j++ = c;
  116.                 } while (--ii);
  117.             }
  118.         }
  119.     for (i = vect, j = high_lim - nbytes_elt; ; ) 
  120.         {
  121.         while (i < mid && compare_elts(i, mid) <= 0)
  122.             i += nbytes_elt;
  123.         while (j > mid) 
  124.             {
  125.             if (compare_elts(mid, j) <= 0) 
  126.                 {
  127.                 j -= nbytes_elt;
  128.                 continue;
  129.                 }
  130.             tmp = i + nbytes_elt;
  131.             if (i == mid) 
  132.                 {
  133.                 mid = jj = j;
  134.                 }
  135.                 else 
  136.                 {
  137.                 jj = j;
  138.                 j -= nbytes_elt;
  139.                 }
  140.             goto swap;
  141.             }
  142.         if (i == mid) 
  143.             {
  144.             break;
  145.             }
  146.             else
  147.             {
  148.             jj = mid;
  149.             tmp = mid = i;
  150.             j -= nbytes_elt;
  151.             }
  152.         swap:
  153.             ii = nbytes_elt;
  154.             do    
  155.                 {
  156.                 c = *i;
  157.                 *i++ = *jj;
  158.                 *jj++ = c;
  159.                 } while (--ii);
  160.             i = tmp;
  161.         }
  162.         i = (j = mid) + nbytes_elt;
  163.         if ((lo = j - vect) <= (hi = high_lim - i)) 
  164.             {
  165.             if (lo >= seg_size)
  166.                 sort_chunk(vect, j);
  167.             vect = i;
  168.             lo = hi;
  169.             }
  170.             else 
  171.             {
  172.             if (hi >= seg_size)
  173.                 sort_chunk(i, high_lim);
  174.             high_lim = j;
  175.             }
  176.         } while (lo >= seg_size);
  177. }
  178.