Блог

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

Это мой первый пост, поэтому извините, если он грязный. Спасибо!

 function merge_sort (src_array)

  if #src_array <= 1 then 
    return src_array 
  else
   local a1, a2 = split_array(src_array)        -- splitting array to sort
   return merge(            -- merge the results recursively
         merge_sort(a1),    
         merge_sort(a2))
   end
end 
 

Я пытаюсь использовать несколько результатов и отслеживать счетчик

Если вы хотите сделать это, используя несколько результатов, вам нужно изменить свой рекурсивный вызов. Каждая функция должна возвращать отсортированный массив вместе с количеством сравнений, необходимых для его сортировки:

 local s1, n1 = merge_sort(a1)
local s2, n2 = merge_sort(a2)
local s, n = merge(s1, s2)
return s, n1   n2   n
 

Ваш базовый вариант будет выглядеть так

 return src_array, 0
 

Я думаю, что, вероятно, дополнительный результат того не стоит, и вам лучше использовать локальный счетчик и вложенную merge функцию:

 function merge_sort (src_array)

  local n = 0   -- number of comparisons

  local function merge(a1, a2)
    -- merge a1 and a2, incrementing n at each comparison
    -- return merged array
  end
  local function sort(a)
    if #a <= 1 then 
      return a
    else
      local a1, a2 = split_array(a)        -- splitting array to sort
      return merge(            -- merge the results recursively
            sort(a1),    
            sort(a2)) -- recursive call to `sort` *not* `merge_sort`
    end
  end
  local sorted = sort(src_array)
  return sorted, n
end 
 

Используйте значение upvalue (i в примере ниже):

 do
    local i = 0
    function foo ()
        if i>= 100 then return i end
        i = i   1
        return foo() foo()
    end
end