?login_element?

Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  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)
  67.