## counting sort

### Data

in lua

#### Tags

distribution sort, sorting, stable sort

### Source Code

``````-- In place counting sort implementation
-- See : http://en.wikipedia.org/wiki/Counting_sort

-- Returns the maximum value of the given array
local function find_max_val(array)
local m = array[1]
for i = 2, #array do
if array[i] > m then
m = array[i]
end
end
return m
end

-- Returns an array of len size, filled with default value
local function make_array(len, default)
local t = {}
for i = 0, len do t[i] = default end
return t
end

-- In-place counting sort implementation
-- array: a given array, to be sorted in-place
-- returns: the passed-in array, sorted.
return function(array)
local m = find_max_val(array) + 1
local count = make_array(m, 0)
for _,v in ipairs(array) do
count[v] = count[v] + 1
end
local i = 1
for j = 0, m do
for c = 1, count[j] do
array[i] = j
i = i + 1
end
end
return array
end
``````
``````-- Tests for countsort.lua
local countsort = require 'countsort'

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

-- Checks if the given array is sorted
local function is_sorted(array)
local m = array[1]
for i = 2,#array do
if i < m then return false end
end
return true
end

run('Array should not be empty', function()
assert(not pcall(countsort, {}))
end)

run('Array can be sorted', function()
assert(is_sorted(countsort({0,1,2,3,4,5,6})))
assert(is_sorted(countsort({6,5,4,3,2,1,0})))
end)

run('Array should not contain negative values', function()
assert(not pcall(countsort, {0,-1,5,3,2}))
end)

run('Array should not contain non-integer values', function()
assert(not pcall(countsort, {0.5,5.5,2,3,2}))
end)

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