home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compcomp / lex / 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.                                 continue;
  63.                         }
  64.                         j -= es;
  65.                         goto loop;
  66.                 }
  67.  
  68.  
  69.                 if(i == lp) {
  70.                         if(lp-a >= l-hp) {
  71.                                 q_sort(hp+es, l);
  72.                                 l = lp;
  73.                         } else {
  74.                                 q_sort(a, lp);
  75.                                 a = hp+es;
  76.                         }
  77.                         goto start;
  78.                 }
  79.                 q_tex(j, lp -= es, i);
  80.                 j = hp -= es;
  81.         }
  82. }
  83.  
  84. q_exc(i, j)
  85. char *i, *j;
  86. {
  87.         register char *ri, *rj, c;
  88.         int n;
  89.  
  90.         n = size;
  91.         ri = i;
  92.         rj = j;
  93.         do {
  94.                 c = *ri;
  95.                 *ri++ = *rj;
  96.                 *rj++ = c;
  97.         } while(--n);
  98. }
  99.  
  100. q_tex(i, j, k)
  101. char *i, *j, *k;
  102. {
  103.         register char *ri, *rj, *rk;
  104.         int c;
  105.         int n;
  106.  
  107.         n = size;
  108.         ri = i;
  109.         rj = j;
  110.         rk = k;
  111.         do {
  112.                 c = *ri;
  113.                 *ri++ = *rk;
  114.                 *rk++ = *rj;
  115.                 *rj++ = c;
  116.         } while(--n);
  117. }
  118.