diff options
author | Jeremy Allison <jra@samba.org> | 2009-10-17 10:36:33 -0700 |
---|---|---|
committer | Jeremy Allison <jra@samba.org> | 2009-10-17 10:36:33 -0700 |
commit | 7c51fa6d699a653cafa90df8e44911b576118ebd (patch) | |
tree | 543bf9ca698e03eff81104898b33e77f1abed319 /source3/lua-5.1.4/test/sort.lua | |
parent | cc3a6770c77ec8fe1cd63bf4c682853c56201f0c (diff) | |
parent | 3e3214fd91471bca5b6c4d3782e922d252d588fb (diff) | |
download | samba-7c51fa6d699a653cafa90df8e44911b576118ebd.tar.gz samba-7c51fa6d699a653cafa90df8e44911b576118ebd.tar.bz2 samba-7c51fa6d699a653cafa90df8e44911b576118ebd.zip |
Merge branch 'master' of ssh://jra@git.samba.org/data/git/samba
Diffstat (limited to 'source3/lua-5.1.4/test/sort.lua')
-rw-r--r-- | source3/lua-5.1.4/test/sort.lua | 66 |
1 files changed, 0 insertions, 66 deletions
diff --git a/source3/lua-5.1.4/test/sort.lua b/source3/lua-5.1.4/test/sort.lua deleted file mode 100644 index 0bcb15f837..0000000000 --- a/source3/lua-5.1.4/test/sort.lua +++ /dev/null @@ -1,66 +0,0 @@ --- two implementations of a sort function --- this is an example only. Lua has now a built-in function "sort" - --- extracted from Programming Pearls, page 110 -function qsort(x,l,u,f) - if l<u then - local m=math.random(u-(l-1))+l-1 -- choose a random pivot in range l..u - x[l],x[m]=x[m],x[l] -- swap pivot to first position - local t=x[l] -- pivot value - m=l - local i=l+1 - while i<=u do - -- invariant: x[l+1..m] < t <= x[m+1..i-1] - if f(x[i],t) then - m=m+1 - x[m],x[i]=x[i],x[m] -- swap x[i] and x[m] - end - i=i+1 - end - x[l],x[m]=x[m],x[l] -- swap pivot to a valid place - -- x[l+1..m-1] < x[m] <= x[m+1..u] - qsort(x,l,m-1,f) - qsort(x,m+1,u,f) - end -end - -function selectionsort(x,n,f) - local i=1 - while i<=n do - local m,j=i,i+1 - while j<=n do - if f(x[j],x[m]) then m=j end - j=j+1 - end - x[i],x[m]=x[m],x[i] -- swap x[i] and x[m] - i=i+1 - end -end - -function show(m,x) - io.write(m,"\n\t") - local i=1 - while x[i] do - io.write(x[i]) - i=i+1 - if x[i] then io.write(",") end - end - io.write("\n") -end - -function testsorts(x) - local n=1 - while x[n] do n=n+1 end; n=n-1 -- count elements - show("original",x) - qsort(x,1,n,function (x,y) return x<y end) - show("after quicksort",x) - selectionsort(x,n,function (x,y) return x>y end) - show("after reverse selection sort",x) - qsort(x,1,n,function (x,y) return x<y end) - show("after quicksort again",x) -end - --- array to be sorted -x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"} - -testsorts(x) |