home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / s5 / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1975-05-13  |  1.3 KB  |  121 lines
  1.  
  2. int    (*qscmp)();
  3. int    qses;
  4.  
  5. qsort(a, n, es, fc)
  6. char *a;
  7. int n, es;
  8. int (*fc)();
  9. {
  10.     qscmp = fc;
  11.     qses = es;
  12.     qs1(a, a+n*es);
  13. }
  14.  
  15. qs1(a, l)
  16. char *a, *l;
  17. {
  18.     register char *i, *j, *es;
  19.     char *lp, *hp;
  20.     int n, c;
  21.  
  22.  
  23.     es = qses;
  24.  
  25. start:
  26.     if((n=l-a) <= es)
  27.         return;
  28.  
  29.  
  30.     n = ((n/(2*es))*es) & 077777;
  31.     hp = lp = a+n;
  32.     i = a;
  33.     j = l-es;
  34.  
  35.  
  36.     for(;;) {
  37.         if(i < lp) {
  38.             if((c = (*qscmp)(i, lp)) == 0) {
  39.                 qsexc(i, lp =- es);
  40.                 continue;
  41.             }
  42.             if(c < 0) {
  43.                 i =+ es;
  44.                 continue;
  45.             }
  46.         }
  47.  
  48. loop:
  49.         if(j > hp) {
  50.             if((c = (*qscmp)(hp, j)) == 0) {
  51.                 qsexc(hp =+ es, j);
  52.                 goto loop;
  53.             }
  54.             if(c > 0) {
  55.                 if(i == lp) {
  56.                     qstexc(i, hp =+ es, j);
  57.                     i = lp =+ es;
  58.                     goto loop;
  59.                 }
  60.                 qsexc(i, j);
  61.                 j =- es;
  62.                 i =+ es;
  63.                 continue;
  64.             }
  65.             j =- es;
  66.             goto loop;
  67.         }
  68.  
  69.  
  70.         if(i == lp) {
  71.             if(lp-a >= l-hp) {
  72.                 qs1(hp+es, l);
  73.                 l = lp;
  74.             } else {
  75.                 qs1(a, lp);
  76.                 a = hp+es;
  77.             }
  78.             goto start;
  79.         }
  80.  
  81.  
  82.         qstexc(j, lp =- es, i);
  83.         j = hp =- es;
  84.     }
  85. }
  86.  
  87. qsexc(i, j)
  88. char *i, *j;
  89. {
  90.     register char *ri, *rj, c;
  91.     int n;
  92.  
  93.     n = qses;
  94.     ri = i;
  95.     rj = j;
  96.     do {
  97.         c = *ri;
  98.         *ri++ = *rj;
  99.         *rj++ = c;
  100.     } while(--n);
  101. }
  102.  
  103. qstexc(i, j, k)
  104. char *i, *j, *k;
  105. {
  106.     register char *ri, *rj, *rk;
  107.     char    c;
  108.     int    n;
  109.  
  110.     n = qses;
  111.     ri = i;
  112.     rj = j;
  113.     rk = k;
  114.     do {
  115.         c = *ri;
  116.         *ri++ = *rk;
  117.         *rk++ = *rj;
  118.         *rj++ = c;
  119.     } while(--n);
  120. }
  121.