## comb sort

in lua

### Source Code

``````-- Comb sort algorithm implementation
-- See: http://en.wikipedia.org/wiki/Comb_sort

-- Performs a Comb sort, in-place
-- list: a list of elements to be sorted, in-place
-- comp : (optional) a comparison function, defaults to function (a,b) return a<b end
-- returns : the passed-in list, sorted in-place
return function (list, comp)
comp = comp or function(a,b) return a<b end
local gap = #list
repeat
gap = math.max(1, math.floor(gap/1.25))
local i, swaps = 1, 0
repeat
if comp(list[i+gap], list[i]) and list[i]~=list[i+gap] then
list[i], list[i+gap] = list[i+gap], list[i]
swaps = 1
end
i = i+1
until i+gap > #list
until gap == 1 and swaps == 0
return list
end``````
``````-- Tests for comb_sort.lua
local comb_sort = require 'comb_sort'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Comparison functions
local function le(a,b) return a <= b end
local function ge(a,b) return a >= b end

-- Checks if list is sorted
function is_sorted(list, comp)
for i = 2, #list do
if not comp(list[i-1],list[i]) then return false end
end
return true
end

-- Generates a table of n random values in [1..n]
local function gen(n)
local t = {}
for i = 1, n do t[i] = math.random(n) end
return t
end

math.randomseed(os.time())

run('Testing Comb sort', function()
assert(is_sorted(comb_sort(gen(100), le), le))
assert(is_sorted(comb_sort(gen(100), ge), ge))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````