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