Merge pull request kennyledet#98 from Yonaba/master

jcla1 · jcla1 · commit 976c13ac3375 · 2014-01-01T08:31:47.000-08:00
Moved .lua files to subfolder
diff --git a/Insertion_Sort/Lua/Yonaba/insertion_sort.lua b/Insertion_Sort/Lua/Yonaba/insertion_sort.lua
@@ -0,0 +1,21 @@
+-- Insertion sort algorithm
+-- See: http://en.wikipedia.org/wiki/Insertion_sort#Algorithm
+
+-- list: a list 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
+return function (list, comp)
+	comp = comp or function(a, b) return a < b end
+	local n = #list
+	for i = 2, n do
+		local x = list[i]
+		local j = i
+		while j>1 and not comp(list[j-1],x) do
+			list[j] = list[j-1]
+			j = j - 1
+		end
+		list[j] = x
+	end
+	return list
+end
diff --git a/Insertion_Sort/Lua/Yonaba/insertion_sort_test.lua b/Insertion_Sort/Lua/Yonaba/insertion_sort_test.lua
@@ -0,0 +1,60 @@
+-- Tests for insertion_sort.lua
+local insertion_sort = require 'insertion_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)
+	comp = comp or le
+	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
+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('Empty arrays', function()
+	local t = {}
+	assert(is_sorted(insertion_sort({})))
+end)
+
+run('Already sorted array', function()
+	local t = {1, 2, 3, 4, 5}
+	assert(is_sorted(insertion_sort(t)))
+end)
+
+run('Sorting a large array (1e3 values)', function()
+	local t = gen(1e3)
+	assert(is_sorted(insertion_sort(t)))
+	assert(is_sorted(insertion_sort(t, ge), ge))
+end)
+
+print(('-'):rep(80))
+print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
+	:format(total, pass, total-pass, (pass*100/total)))
diff --git a/Quick_Sort/Lua/Yonaba/quick_sort.lua b/Quick_Sort/Lua/Yonaba/quick_sort.lua
@@ -30,9 +30,10 @@ end
 
 -- Quicksort function wrapper, to shadow access 
 -- to left and right bounds
--- list: a list to be ordered
+-- list: a list to be ordered, in-place
 -- comp: (optional) a comparison function
 --  defaults to function(a, b) return a < b end
+-- returns: the passed-in list, sorted
 return function (list, comp)
 	comp = comp or function(a, b) return a < b end
 	return quicksort(list, comp)
diff --git a/Quick_Sort/Lua/Yonaba/quick_sort_test.lua b/Quick_Sort/Lua/Yonaba/quick_sort_test.lua
