Home > Mobile >  How to Sort a table of strings according to the order defined by another table of strings (Lua)
How to Sort a table of strings according to the order defined by another table of strings (Lua)

Time:11-08

I have 2 lua tables:

OrderTbl = {'Hello', 'Question', 'Answer', 'Bye'}
UnsortedTbl = {'Question', 'Bye, 'Bye', 'Question', 'Hello', 'Something'}

How to sort UnsortedTbl in order given by OrderTbl? (Fields not found in OrderTbl are placed in the end of result table, unsorted)

I have translated a sample of code from Java, and it works with numbers. Here it is:

function first(arr, low, high, x, n)
    if high >= low then
    
        -- (low   high)/2
        local mid = low   math.floor((high - low) / 2)
        
        if (mid == 1 or x > arr[mid - 1]) and arr[mid] == x then
            return mid
        end
        if x > arr[mid] then return first(arr, (mid   1), high, x, n) end
        return first(arr, low, (mid - 1), x, n)
    end
    return nil
end

-- Sort A1 according to the order
-- defined by A2
function sortAccording(A1, A2)
    local m=#A1
    local n=#A2

    -- The temp array is used to store a copy
    -- of A1{} and visited{} is used to mark the
    -- visited elements in temp{}.
    local temp = {}
    local visited = {}

    for i = 1, m do
        temp[i] = A1[i]
        visited[i] = 0
    end

    -- Sort elements in temp
    table.sort(temp)

    -- for index of output which is sorted A1{}
    local ind = 0

    -- Consider all elements of A2{}, find them
    -- in temp{} and copy to A1{} in order.
    for i = 1, n do
        -- Find index of the first occurrence
        -- of A2[i] in temp
        local f = first(temp, 1, m, A2[i], m 1)
        -- If not present, no need to proceed
        if not f then
            -- continue
        else
            -- Copy all occurrences of A2[i] to A1{}
            j = f
            while j < m and temp[j] == A2[i] do
                A1[ind] = temp[j]
                ind = ind   1
                visited[j] = 1
                j = j   1
            end
        end
    end
    -- Now copy all items of temp{} which are
    -- not present in A2{}
    for i = 1, m do
        if visited[i] == 0 then
            ind = ind   1
            A1[ind] = temp[i]
        end
    end

end

function printArray(arr)
    for i = 1, #arr do 
        print(arr[i] .. " ") 
    end
end

-- Driver program to test above function.
local A1 = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
local A2 = {2, 1, 4, 3, 6, 5, 8, 7}

sortAccording(A1, A2)
printArray(A1)

I don't quite understand how to make it work with strings. Could you help me?

CodePudding user response:

You can use the form of table.sort that accepts a custom comparator:

local OrderTbl = {'Hello', 'Question', 'Answer', 'Bye'}
local UnsortedTbl = {'Question', 'Bye', 'Bye', 'Question', 'Hello', 'Something', 'Else'}

-- convert the order to hash that can be easily queried
for idx, val in ipairs(OrderTbl) do OrderTbl[val] = idx end

local maxIdx = #OrderTbl   1 -- this will mark "missing" elements
-- pass a custom comparator that will check OrderTbl
table.sort(UnsortedTbl, function(a, b)
    local pa = OrderTbl[a] or maxIdx -- desired index of a
    local pb = OrderTbl[b] or maxIdx -- desired index of b
    if pa == pb then return a < b end -- sort by name
    return pa < pb -- sort by index
  end)
  • Related