codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# heap sort 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] } # simple heap sort function swap(A,i,j, t) { t = A[i]; A[i] = A[j]; A[j] = t } function heapify(A,left,right, p,c) { for (p=left; (c=2*p) <= right; p=c) { if (c<right && A[c] < A[c+1]) c++ if (A[p] < A[c]) swap(A, c, p) } } function sort(A,n, i) { for (i=int(n/2); i>=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { swap(A, 1, i) heapify(A, 1, i-1) } } # move swap inline, move invariant part of swap out of inner loop function heapify(A,left,right, p,c,t) { t = A[left] for (p=left; (c=2*p) <= right; p=c) { if (c<right && A[c] < A[c+1]) c++ if (t < A[c]) A[p] = A[c]; else break } A[p] = t } function sort(A,n, i,t) { for (i=int(n/2); i>=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { t = A[1]; A[1] = A[i]; A[i] = t heapify(A, 1, i-1) } } # sift all the way down, then back up function heapify(A,left,right, p,c,t) { t = A[left] for (p=left; (c=2*p) <= right; p=c) { if (c<right && A[c] < A[c+1]) c++ A[p] = A[c] } for (c=p; (p=int(c/2)) >= left; c=p) { if (t > A[p]) A[c] = A[p]; else break } A[c] = t } function sort(A,n, i,t) { for (i=int(n/2); i>=1; i--) heapify(A, i, n) for (i=n; i>1; i--) { t = A[1]; A[1] = A[i]; A[i] = t heapify(A, 1, i-1) } } # move heapify code inline function sort(A,n, l,r,p,c,t) { if (n > 1) { l = int(n/2) + 1; r = n while(1) { if (l > 1) t = A[--l] else { t = A[r]; A[r--] = A[1] if (r == 1) { A[1] = t; return } } for (p=l; (c=2*p) <= r; p=c) { if (c < r && A[c] < A[c+1]) c++ A[p] = A[c] } for (c=p; (p=int(c/2)) >= l; c=p) { if (A[p] < t) A[c] = A[p]; else break } A[c] = t } } }
Private
[
?
]
Run code
Submit