# Standards

Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

## Tuesday, September 18, 2012

### Quicksort in Lua

``````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, 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, _(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)
``````