diff options
author | Matthew Sotoudeh <matthew@masot.net> | 2024-05-17 15:57:30 -0700 |
---|---|---|
committer | Matthew Sotoudeh <matthew@masot.net> | 2024-05-17 15:57:30 -0700 |
commit | d068f0b3c11348a50c18af1ee3b0d2e5f38c4faf (patch) | |
tree | db777acca2336f8c279e9f09346f02de7ddaa0e9 /lua_benchmark/tests/Lua-Benchmarks/heapsort.lua | |
parent | 221b05e7a86faa38036429d5fbfc8b0779eb5382 (diff) |
lua benchmarks
Diffstat (limited to 'lua_benchmark/tests/Lua-Benchmarks/heapsort.lua')
-rw-r--r-- | lua_benchmark/tests/Lua-Benchmarks/heapsort.lua | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/lua_benchmark/tests/Lua-Benchmarks/heapsort.lua b/lua_benchmark/tests/Lua-Benchmarks/heapsort.lua new file mode 100644 index 0000000..0aaf7cb --- /dev/null +++ b/lua_benchmark/tests/Lua-Benchmarks/heapsort.lua @@ -0,0 +1,48 @@ +local random, floor = math.random, math.floor
+floor = math.ifloor or floor
+
+function heapsort(n, ra)
+ local j, i, rra
+ local l = floor(n/2) + 1
+ -- local l = (n//2) + 1
+ local ir = n;
+ while 1 do
+ if l > 1 then
+ l = l - 1
+ rra = ra[l]
+ else
+ rra = ra[ir]
+ ra[ir] = ra[1]
+ ir = ir - 1
+ if (ir == 1) then
+ ra[1] = rra
+ return
+ end
+ end
+ i = l
+ j = l * 2
+ while j <= ir do
+ if (j < ir) and (ra[j] < ra[j+1]) then
+ j = j + 1
+ end
+ if rra < ra[j] then
+ ra[i] = ra[j]
+ i = j
+ j = j + i
+ else
+ j = ir + 1
+ end
+ end
+ ra[i] = rra
+ end
+end
+
+local Num = tonumber((arg and arg[1])) or 4
+for i=1,Num do
+ local N = tonumber((arg and arg[2])) or 10000
+ local a = {}
+ for i=1,N do a[i] = random() end
+ heapsort(N, a)
+ for i=1,N-1 do assert(a[i] <= a[i+1]) end
+end
+
|