sort.c

Go to the documentation of this file.

int in[] = {10, 32, -1, 567, 3, 18, 1, -51, 789, 0};

main() {
    int i;

    sort(in, (sizeof in)/(sizeof in[0]));
    for (i = 0; i < (sizeof in)/(sizeof in[0]); i++) {
        putd(in[i]);
        putchar('\n');
    }
    return 0;
}

/* putd - output decimal number */
putd(n) {
    if (n < 0) {
        putchar('-');
        n = -n;
    }
    if (n/10)
        putd(n/10);
    putchar(n%10 + '0');
}

int *xx;

/* sort - sort a[0..n-1] into increasing order */
sort(a, n) int a[]; {
    quick(xx = a, 0, --n);
}

/* quick - quicksort a[lb..ub] */
quick(a, lb, ub) int a[]; {
    int k, partition();

    if (lb >= ub)
        return;
    k = partition(a, lb, ub);
    quick(a, lb, k - 1);
    quick(a, k + 1, ub);
}

/* partition - partition a[i..j] */
int partition(a, i, j) int a[]; {
    int v, k;

    j++;
    k = i;
    v = a[k];
    while (i < j) {
        i++; while (a[i] < v) i++;
        j--; while (a[j] > v) j--;
        if (i < j) exchange(&a[i], &a[j]);
    }
    exchange(&a[k], &a[j]);
    return j;
}

/* exchange - exchange *x and *y */
exchange(x, y) int *x, *y; {
    int t;

    printf("exchange(%d,%d)\n", x - xx, y - xx);
    t = *x; *x = *y; *y = t;
}

---