Re: The Alphanum Algorithm for Lua

[Nick Gammon <nick@...>]

The only problem with the version shown earlier is that the chunking  
is done for every comparison. A quick test shows that for a table of  
70 items you might be calling the chunk routine 800 times.

The variant below does a chunking pass once, storing the results in a  
temporary table as an upvalue, and then uses that for the comparison.  
In my timing test it was about 4 times faster.

------

function alphanum (t)
  assert (type (t) == "table", "Must pass table to be sorted to  
alphanum")

  local function chunkString(str)
  local c = {}
  for a, b in tostring (str):gmatch("(%d*)(%D*)") do
     if a ~= "" then c[#c+1] = tonumber(a) end
     if b ~= "" then c[#c+1] = b end
    end
    return c
  end

  local chunks = {}
  -- build temporary table of the keys
  for i=1, #t do
   chunks [t [i]] = chunkString (t [i])
  end

  return function (a, b) -- return our sort comparison function

   -- lookup chunked information from previously-built table
   local achunks = chunks [a]
   local bchunks = chunks [b]

   for i = 1, math.min (#achunks, #bchunks) do
      local as, bs = achunks [i], bchunks [i]

      -- if one is a string, make them both strings
      if type (as) == "string" or type (bs) == "string"  then
        as = (tostring (as)):upper ()
        bs = (tostring (bs)):upper ()
      end -- at least one is a string

      -- if they are equal, move onto the next chunk
      if as ~= bs then
        return as < bs
      end  -- if
   end  -- for each chunk

   -- still equal? the one with fewer chunks compares less
   return #achunks < #bchunks

  end  -- sort function

end -- alphanum


--  Example:

t={
"z18.doc","z19.doc","z2.doc","z16.doc","z17.doc",  
"z1.doc","z101.doc","z102.doc","z11.doc","z12.doc",
"z13.doc","z14.doc","z15.doc","z20.doc","z3.doc",  
"z4.doc","z5.doc","z6.doc","z10.doc","z100.doc",
"z7.doc","z8.doc","z9.doc",
}

table.sort(t, alphanum (t))

for i=1, #t do
   print(t[i])
end