Сортировка Radix не работает в Lua

Question

Во-первых, я должен отметить, что я вообще не кодировал очень долго, хотя это, вероятно, очевидно из моего кода: P

У меня две проблемы, во-первых, сортировка не работает правильно, но сортирует числа по длине. Любая помощь здесь будет оценена.

Во-вторых, меняется таблица, которую он захватывает, и таблица, которую он возвращает (не знаю, почему). Как я могу предотвратить изменение таблицы, которую он захватывает?

Я бы предпочел, чтобы люди не публиковали полностью оптимизированный готовый код, так как я не собираюсь ничего учить или понимать таким образом.

function radix_sort(x)

   pass, bucket, maxstring = 0, x, 2 

   while true do

      pass = pass + 1
      queue = {}

      for n=#bucket,1,-1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         if pass == 1 and key_length > maxstring then
            maxstring = key_length
         end

         if key_length == pass then
            pool = string.sub(key, 1,1) 

            if queue[pool + 1] == nil then
               queue[pool + 1] = {}
            end 

            table.insert(queue[pool + 1], key)
            table.remove(bucket, n)
         end
      end

      for k,v in pairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end            
      end

      if pass == maxstring then
         break
      end
   end

   return bucket
end

Answer 1

Я сделал много изменений, чтобы заставить это работать, так что, надеюсь, вы сможете просмотреть их и узнать о них. Я старался комментировать как мог.

function radix_sort(x)

   pass, maxstring = 0, 0 

   -- to avoid overwriting x, copy into bucket like this
   -- it also gives the chance to init maxstring
   bucket={}
   for n=1,#x,1 do
      -- since we can, convert all entries to strings for string functions below
      bucket[n]=tostring(x[n])
      key_length = string.len(bucket[n])
      if key_length > maxstring then
         maxstring = key_length
      end
   end

   -- not a fan of "while true ... break" when we can set a condition here
   while pass <= maxstring do

      pass = pass + 1

      -- init both queue and all queue entries so ipairs doesn't skip anything below
      queue = {}
      for n=1,10,1 do
         queue[n] = {}
      end

      -- go through bucket entries in order for an LSD radix sort
      for n=1,#bucket,1 do

         key_length = string.len(bucket[n])
         key = bucket[n]

         -- for string.sub, start at end of string (LSD sort) with -pass
         if key_length >= pass then
            pool = tonumber(string.sub(key, pass*-1, pass*-1))
         else
            pool = 0
         end

         -- add to appropriate queue, but no need to remove from bucket, reset it below
         table.insert(queue[pool + 1], key)
      end

      -- empty out the bucket and reset, use ipairs to call queues in order
      bucket={}
      for k,v in ipairs(queue) do
         for n=1,#v do
            table.insert(bucket, v[n])
         end            
      end
   end

   return bucket
end

Вот тестовый прогон:

> input={55,2,123,1,42,9999,6,666,999,543,13}
> output=radix_sort(input)
> for k,v in pairs(output) do
>   print (k , " = " , v)
> end
1    =  1
2    =  2
3    =  6
4    =  13
5    =  42
6    =  55
7    =  123
8    =  543
9    =  666
10   =  999
11   =  9999

Answer 2

        pool = string.sub(key, 1,1) 

всегда смотрит на первый символ; возможно вы имели ввиду string.sub(key, pass, 1)