Project:
 Link:    [ raw code | fork ]

Plain Text, pasted on Nov 8:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 ``` ```# two linear sorts BEGIN { for (i=0; i<=20; i++) tester(i) tester(1000) } function tester(i) { genid(x,i); sort(x,i); check(x,i); clear(x) gensort(x,i); sort(x,i); check(x,i); clear(x) genrev(x,i); sort(x,i); check(x,i); clear(x) genrand(x,i); sort(x,i); check(x,i); clear(x) } function genid(x,n, i) { for (i=1; i<=n; i++) x[i] = 1 } function gensort(x,n, i) { for (i=1; i<=n; i++) x[i] = i } function genrev(x,n, i) { for (i=1; i<=n; i++) x[i] = n + 1 - i } function genrand(x,n, i) { for (i=1; i<=n; i++) x[i] = int(n * rand()) } function check(x,n, i) { for (i=1; i= 0; i--) t[s[A[i]]--] = A[i] for (i = 0; i <= n; i++) A[i] = t[i] } # radix sort function digit(x,k) { while (k-- > 0) x = int(x / 10) return x % 10 } function sort(A,n, b,m,p,i,s,t) { for (m = 1; m <= n; m *= 10) b++ for (p = 0; p < b; p++) { for (i = 0; i < 10; i++) s[i] = 0 for (i = 1; i <= n; i++) s[digit(A[i], p)]++ for (i = 1; i < 10; i++) s[i] += s[i-1] for (i = n; i >= 1; i--) { t[s[digit(A[i], p)]] = A[i] s[digit(A[i], p)]-- } for (i = 1; i <= n; i++) A[i] = t[i] } } ```