function rest(xs)
local ys = {}
for i = 2, #xs do
table.insert(ys, xs[i])
end
return ys
end
function concat(xs, ys)
local zs = {}
for _, v in ipairs(xs) do
table.insert(zs, v)
end
for _, v in ipairs(ys) do
table.insert(zs, v)
end
return zs
end
function qsort(xs)
if (#xs < 2) then
return xs
end
local p, xs = xs[1], rest(xs)
local lesser, greater = {}, {}
for _, x in ipairs(xs) do
if x < p then
table.insert(lesser, x)
else
table.insert(greater, x)
end
end
return concat(qsort(lesser), concat({p}, qsort(greater)))
end
xs = {3, 1, 4, 1, 5, 9}
for _, x in ipairs(qsort(xs)) do
io.write(x .. ' ')
end
print()
-- to check if the original xs isn't destroyed
for _, x in ipairs(xs) do
io.write(x .. ' ')
end
This works, but the code looks more complicated than it should be.
I rewrote it with using Underscore.lua and it made the code much easier to read.
_ = require 'underscore'
function concat(xs, ys)
return _(ys):reduce(xs, function(m, x)
return _(m):push(x)
end)
end
function qsort(xs)
if (#xs < 2) then
return xs
end
local p, xs = xs[1], _(xs):rest()
return concat(
_(qsort(_(xs):select(function(x) return x < p end))):push(p),
qsort(_(xs):select(function(x) return x >= p end)))
end
xs = {3, 1, 4, 1, 5, 9}
_(qsort(xs)):each(function(x)
io.write(x .. ' ')
end)
print()
_(xs):each(function(x)
io.write(x .. ' ')
end)
