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
69
70
71
72
73
74
75
76
77
78
79
80
local function prequire(name) local success, result = pcall(require, name); return success and result end
local bench = script and require(script.Parent.bench_support) or prequire("bench_support") or require("../bench_support")
function test()
-- 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"}
local ts0 = os.clock()
for loops=1,10000 do
testsorts(x)
end
local ts1 = os.clock()
return ts1 - ts0
end
bench.runCode(test, "qsort")