sort.c (1051B)
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 }