Added Cocktail sort in Lua

Yonaba · Yonaba · commit cac39db04885 · 2014-02-06T19:08:26.000Z
diff --git a/Cocktail_Sort/Lua/Yonaba/cocktail_sort.lua b/Cocktail_Sort/Lua/Yonaba/cocktail_sort.lua
@@ -0,0 +1,32 @@
+-- (Optimized) Cocktail sort implementation
+-- See: http://en.wikipedia.org/wiki/Cocktail_sort
+
+
+-- list: a list to be sorted (in-place)
+-- comp : (Optional) a comparison function
+--  defaults to function(a,b) return a < b end
+return function (list, comp)
+  comp = comp or function(a,b) return a < b end
+  local begin, _end = 0, #list - 1
+
+  repeat
+    local swapped = false
+    begin = begin + 1
+    for i = begin, _end do
+      if not comp(list[i], list[i+1]) then
+        list[i], list[i+1] = list[i+1], list[i]
+        swapped = true
+      end
+    end
+    if not swapped then break end
+    _end = _end - 1
+    for i = _end, begin, -1 do
+      if not comp(list[i], list[i+1]) then
+        list[i], list[i+1] = list[i+1], list[i]
+        swapped = true
+      end
+    end
+  until not swapped
+  return list
+end
+
diff --git a/Cocktail_Sort/Lua/Yonaba/cocktail_sort_test.lua b/Cocktail_Sort/Lua/Yonaba/cocktail_sort_test.lua
@@ -0,0 +1,87 @@
+-- Tests for cocktail_sort.lua
+local cocktail_sort = require 'cocktail_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
+
+-- Wrap for Lua's table sort so that it returns
+-- the passed-in table
+local function sort(t, comp)
+  table.sort(t, comp)
+  return t
+end
+
+-- Returns a copy of a an array
+local function clone(t)
+  local _t = {}
+  for k,v in ipairs(t) do _t[k] = v end
+  return _t
+end
+
+-- Checks if t1 and t2 arrays are the same
+local function same(t1, t2)
+  for k,v in ipairs(t1) do
+    if t2[k] ~= v then return false end
+  end
+  return true
+end
+
+-- Generates an array of n values in random order
+local function gen(n)
+  local t = {}
+  for i = 1, n do t[i] = math.random(n) end
+  return t
+end
+
+-- Note: Let's add a bit of randomness
+math.randomseed(os.time())
+
+run('Empty arrays', function()
+  local t = {}
+  assert(same(sort(clone(t)),cocktail_sort(t)))
+end)
+
+run('Sorted array', function()
+  local t = {1, 2, 3, 4, 5}
+  assert(same(sort(clone(t)),cocktail_sort(t)))
+end)
+
+run('Array sorted in reverse', function()
+  local t = {5, 4, 3, 2, 1}
+  assert(same(sort(clone(t)),cocktail_sort(t)))
+  local t = {5, 4, 3, 2, 1}
+  local comp = function(a,b) return a>b end
+  assert(same(sort(clone(t), comp),cocktail_sort(t, comp)))
+end)
+
+run('Array containing multiple occurences of the same value', function()
+  local t = {4, 4, 8, 2, 2}
+  local comp = function(a,b) return a <= b end
+  assert(same(sort(clone(t)),cocktail_sort(t, comp)))
+  local t = {0, 0, 0, 0, 0}
+  local comp = function(a,b) return a <= b end
+  assert(same(sort(clone(t)),cocktail_sort(t, comp)))
+end)
+
+run('Large array of random values (1e3 values)', function()
+  local t = gen(1e3)
+  local comp = function(a,b) return a <= b end
+  assert(same(sort(clone(t)),cocktail_sort(t, comp)))
+end)
+
+print(('-'):rep(80))
+print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
+  :format(total, pass, total-pass, (pass*100/total)))
diff --git a/Cocktail_Sort/tags b/Cocktail_Sort/tags
@@ -0,0 +1 @@
+Sorting,Exchange sort
