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