compilers/lcc-4.2/tst/sort.c

   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 }