test/sort.lua

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