]> git.saurik.com Git - redis.git/blame_incremental - deps/lua/test/sort.lua
merge conflicts resolved
[redis.git] / deps / lua / test / sort.lua
... / ...
CommitLineData
1-- two implementations of a sort function
2-- this is an example only. Lua has now a built-in function "sort"
3
4-- extracted from Programming Pearls, page 110
5function qsort(x,l,u,f)
6 if l<u then
7 local m=math.random(u-(l-1))+l-1 -- choose a random pivot in range l..u
8 x[l],x[m]=x[m],x[l] -- swap pivot to first position
9 local t=x[l] -- pivot value
10 m=l
11 local i=l+1
12 while i<=u do
13 -- invariant: x[l+1..m] < t <= x[m+1..i-1]
14 if f(x[i],t) then
15 m=m+1
16 x[m],x[i]=x[i],x[m] -- swap x[i] and x[m]
17 end
18 i=i+1
19 end
20 x[l],x[m]=x[m],x[l] -- swap pivot to a valid place
21 -- x[l+1..m-1] < x[m] <= x[m+1..u]
22 qsort(x,l,m-1,f)
23 qsort(x,m+1,u,f)
24 end
25end
26
27function selectionsort(x,n,f)
28 local i=1
29 while i<=n do
30 local m,j=i,i+1
31 while j<=n do
32 if f(x[j],x[m]) then m=j end
33 j=j+1
34 end
35 x[i],x[m]=x[m],x[i] -- swap x[i] and x[m]
36 i=i+1
37 end
38end
39
40function show(m,x)
41 io.write(m,"\n\t")
42 local i=1
43 while x[i] do
44 io.write(x[i])
45 i=i+1
46 if x[i] then io.write(",") end
47 end
48 io.write("\n")
49end
50
51function testsorts(x)
52 local n=1
53 while x[n] do n=n+1 end; n=n-1 -- count elements
54 show("original",x)
55 qsort(x,1,n,function (x,y) return x<y end)
56 show("after quicksort",x)
57 selectionsort(x,n,function (x,y) return x>y end)
58 show("after reverse selection sort",x)
59 qsort(x,1,n,function (x,y) return x<y end)
60 show("after quicksort again",x)
61end
62
63-- array to be sorted
64x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"}
65
66testsorts(x)