# Sorting part of a list

4 messages
Open this post in threaded view
|

## Sorting part of a list

 I've recently tried to implement an algorithm that requires sorting just a section of an array at a time. Unless I'm missing something this requires making copies of the sub-array in Lua which is sub-optimal. Would it be possible to change (using the syntax from the reference manual): table.sort(list [, comp])   to table.sort(list, [, comp [, i [, j]]]) Where i and j are the first and last indexes to sort between and they default to 1 and #list respectively. Daniel Slaney
Open this post in threaded view
|

## Re: Sorting part of a list

 Op 18 april 2012 12:18 heeft Daniel Slaney <[hidden email]> het volgende geschreven: > I've recently tried to implement an algorithm that requires sorting just > a section of an array at a time. > > Unless I'm missing something this requires making copies of the > sub-array in Lua which is sub-optimal. > You could make a proxy table for the subarray. function slice(tbl,i,j)    local t={}    local origin=i-1    setmetatable(t,{ __len=function(self) return j-origin end; __index=function(self,k) return tbl[k+origin] end; __newindex=function(self,k,v) tbl[k+origin]=v end; })    return t end That will work for Lua-based routines but not for the routines in the table library since "For performance reasons, all table accesses (get/set) performed by these functions are raw. " > Would it be possible to change (using the syntax from the reference > manual): > > table.sort(list [, comp]) > >  to > > table.sort(list, [, comp [, i [, j]]]) > > Where i and j are the first and last indexes to sort between and they > default to 1 and #list respectively. It would be trivial in the C source for Lua.  There is already a function `auxsort` that does just that, called as` auxsort(L, 1, n)` from `sort`. You just need a couple of extra statements to pop i and j from the stack. I'll support a proposal for this change to be mainstream. 1. Generalizes an existing feature without breaking anything. 2. No performance hit.