quick sort, Lua - rextester

quick sort

function table.length(T)
    local size = 0
    for k,v in pairs(T) do
        size = size + 1
    end
    return size
end

function table.tostring(A)
    local size = table.length(A)
    local string = "{"
    for i,v in ipairs(A) do
        string = string .. (v or "")
        if i < size then
           string = string .. ","
        end
    end
    string = string .. "}"
    return string
end

function quickSort(array, p, r)
    p = p or 1
    r = r or #array
    if p < r then
        q = partition(array, p, r)
        quickSort(array, p, q - 1)
        quickSort(array, q + 1, r)
    end
end

function partition(array, p, r)
    local x = array[r]
    local i = p - 1
    for j = p, r - 1 do
        if array[j] <= x then
            i = i + 1
            local temp = array[i]
            array[i] = array[j]
            array[j] = temp
        end
    end
    local temp = array[i + 1]
    array[i + 1] = array[r]
    array[r] = temp
    return i + 1
end

local A = {12,5,4,21,1,2,6,8}

print("In: " .. table.tostring(A).."\n")
quickSort(A)
print("\nOut: " .. table.tostring(A))


run \| edit \| history \| help	0