codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# two sub-quadratic 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<n; i++) if (x[i+1]+0 < x[i]+0) { printf "error in sort" exit } } function clear(x, i) { for (i in x) delete x[i] } function sort(A,n, gap,i,switched,t) { gap = n do { if (gap > 1) gap = int(gap / 1.3) switched = 0 for (i=1; i<=n-gap; i++) if (A[i+gap] < A[i]) { t = A[i]; A[i] = A[i+gap]; A[i+gap] = t switched = 1 } } while (switched || gap > 1) } function sort(A,n, gap,i,j,t) { while (gap < n) gap = 3 * gap + 1 while (gap > 1) { gap = int(gap / 3) for (i=gap+1; i<=n; i++) { t = A[i] for (j=i; gap<j && t<A[j-gap]; j-=gap) A[j] = A[j-gap] A[j] = t } } }
Private
[
?
]
Run code
Submit