Return to sort.c CVS log

Up to [Research Unix] / researchv10dc / cmd / lcc / tst

Annotation of researchv10dc/cmd/lcc/tst/sort.c, revision 1.1.1.1

1.1       root        1: int in[] = {10, 32, -1, 567, 3, 18, 1, -51, 789, 0};
                      2: 
                      3: main() {
                      4:        int i;
                      5: 
                      6:        sort(in, (sizeof in)/(sizeof in[0]));
                      7:        for (i = 0; i < (sizeof in)/(sizeof in[0]); i++) {
                      8:                putd(in[i]);
                      9:                putchar('\n');
                     10:        }
                     11:        return 0;
                     12: }
                     13: 
                     14: /* putd - output decimal number */
                     15: putd(n) {
                     16:        if (n < 0) {
                     17:                putchar('-');
                     18:                n = -n;
                     19:        }
                     20:        if (n/10)
                     21:                putd(n/10);
                     22:        putchar(n%10 + '0');
                     23: }
                     24: 
                     25: int *xx;
                     26: 
                     27: /* sort - sort a[0..n-1] into increasing order */
                     28: sort(a, n) int a[]; {
                     29:        quick(xx = a, 0, --n);
                     30: }
                     31: 
                     32: /* quick - quicksort a[lb..ub] */
                     33: quick(a, lb, ub) int a[]; {
                     34:        int k, partition();
                     35: 
                     36:        if (lb >= ub)
                     37:                return;
                     38:        k = partition(a, lb, ub);
                     39:        quick(a, lb, k - 1);
                     40:        quick(a, k + 1, ub);
                     41: }
                     42: 
                     43: /* partition - partition a[i..j] */
                     44: int partition(a, i, j) int a[]; {
                     45:        int v, k;
                     46: 
                     47:        j++;
                     48:        k = i;
                     49:        v = a[k];
                     50:        while (i < j) {
                     51:                i++; while (a[i] < v) i++;
                     52:                j--; while (a[j] > v) j--;
                     53:                if (i < j) exchange(&a[i], &a[j]);
                     54:        }
                     55:        exchange(&a[k], &a[j]);
                     56:        return j;
                     57: }
                     58: 
                     59: /* exchange - exchange *x and *y */
                     60: exchange(x, y) int *x, *y; {
                     61:        int t;
                     62: 
                     63:        printf("exchange(%d,%d)\n", x - xx, y - xx);
                     64:        t = *x; *x = *y; *y = t;
                     65: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.