root/src/lua-5.1.3/test/sort.lua

Revision 5c8778c4361d2ad3adc94ef98d804c6fa9e6ba7c, 1.5 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 10 years ago)

import lua... I'd like to write checkers in lua

  • Property mode set to 100644
Line 
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
5 function 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
25 end
26
27 function 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
38 end
39
40 function 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")
49 end
50
51 function 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)
61 end
62
63 -- array to be sorted
64 x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"}
65
66 testsorts(x)
Note: See TracBrowser for help on using the browser.