Quicksort em Lua

[Lordfire 110]

Essa função eu já havia feito há muito tempo, e estava aqui guardada sem uso. Pra quem não conhece, o quicksort é um método de ordenação muito eficiente que usa a estratégia de divide and conquer (dividir e conquistar), ou seja, ele divide uma conjunto em conjuntos menores e ordena a partir deles, fazendo isso de um jeito muito rápido.

 

Para você ter ideia, no meu computador ele ordena 10 mil números inteiros aleatórios usando em ordem crescente em menos de 20 ms. Vou postar meu array-exemplo no final.

 

O algoritmo funciona da seguinte forma: o elemento central do array, denominado "pivô", é selecionado; percorrendo o array, todos os valores logicamente menores que este pivô são colocados antes dele, e todos os valores logicamente maiores são colocados depois. Com isso, o pivô fica na sua posição final e tenho dois subconjuntos desordenados; repito estes passos em cada um dos subconjuntos, e assim recursivamente até o conjunto estar completamente ordenado em no máximo n² passos no pior caso possível.

 

function quicksort(arr, comparison, left, right)
   left, right = left ~= nil and left or 1, right ~= nil and right or #arr
   comparison = type(comparison) == 'function' and comparison or function(a, 
       return a <= b
   end


   function partition(arr, left, right, index, comparison)
       local pivot, _index = arr[index], left
       arr[index], arr[right] = arr[right], arr[index]

       for i = left, right - 1 do
           if comparison(arr[i], pivot) then
               arr[i], arr[_index] = arr[_index], arr[i]
               _index = _index + 1
           end
       end
       arr[_index], arr[right] = arr[right], arr[_index]
       return _index
   end


   if right > left then
       local new_index = partition(arr, left, right, math.floor((left + right) / 2), comparison)
       quicksort(arr, comparison, left, new_index - 1)
       quicksort(arr, comparison, new_index + 1, right)
   end
end

 

Note que não há retorno, ou seja, a função é executada in place, o array passado como parâmetro é modificado, e não feito uma cópia. Por isso, ao usar, tome cuidado, pois o array original será perdido se não for feita uma cópia.

 

Você pode opcionalmente informar 3 parâmetros: comparison, left e right. O primeiro é uma função que retorna true se o primeiro parâmetro desta função é logicamente menor que o segundo (ou seja, comparison(a, retorna true se a <= . Left e right devem ser informados se você quer somente ordenar uma parte do array.

 

Array que usei como exemplo (apenas inteiros): https://gist.githubusercontent.com/ranisalt/b76dee806caa3dcbf746/raw/7e608644b47e1707a8a5f2e0a9a9ae3db0a4ee97/gistfile1.lua

 

Essa função tem pouco uso prático dentro de OTServ, mas você pode estudar o funcionamento e a otimização dela. Talvez você queira ordenar os players online pelo level (do mais baixo para o mais alto), ou pelo que tem o level mais próximo de 100 (do mais afastado para o mais próximo). Você pode usar da seguinte forma:

 

players = getOnlinePlayers()
quicksort(players, function(a, 
   return getPlayerLevel(a) <= getPlayerLevel(
end

players = getOnlinePlayers()
quicksort(players, function(a, 
   return math.abs(getPlayerLevel(a) - 100) >= math.abs(getPlayerLevel( - 100)
end

 

Compreendido? Façam bom uso

[Oneshot 24]

Certo, interessante, nunca tinha pensado em um algoritmo do tipo, mas qual a vantagem dessa função sobre table.sort? Menor consumo de memória? Menor processamento?

[Lordfire 110]

Não chega a ter diferença da função built-in porque ela usa quicksort também: https://github.com/LuaDist/lua/blob/master/src/ltablib.c#L155

A diferença é que em Lua puro é muito mais fácil entender a performance é basicamente a mesma.

[Oneshot 24]

derp

 

Nem sabia disso e olha que achava que manjava de Lua rs