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