bogobogosort


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Bogobogosort description
-- See : http://www.dangermouse.net/esoteric/bogobogosort.html

-- A custom array shuffle implementation
-- This is not part of the Bogobogosort algorithm
local function shuffle(list, s, e)
	local n = #list
  for i = s + 1, e do
		local j, k = math.random(s, e), math.random(s, e)
		list[j], list[k] = list[k], list[j]
  end
  return list
end

-- Checks if an array is sorted
local function is_sorted(array, comp, s, e)
  for i = s + 1, e do
    if not comp(array[i-1], array[i]) then
      return false
    end
  end
  return true
end

-- Performs Bogosort between indices i and j
local function bogosort(t, comp, s, e)
  while not is_sorted(t, comp, s, e) do
    shuffle(t, s, e)
  end
	return t
end

-- The Bogobogosort implementation:
-- tbl  : a given table to be sorted
-- comp : (Optional) a comparison function.
--   defaults to function(a,b) return a < b end
-- Note: It is advised to use math.randomseed(os.time())
-- before calling this function. Lua's math.random() is
-- naturally deterministic and since Bogobogosort is based on
-- random shuffling, this is necessary to avoid infinite loops
-- See :
return function(tbl, comp)
  local array_len = #tbl
  comp = comp or function(a, b) return a < b end
  for bound = 2, array_len do
    bogosort(tbl, comp, 1, bound)
  end
  return tbl
end
-- Tests for bogobogosort.lua
local bogobogosort = require 'bogobogosort'

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


math.randomseed(os.time())

-- Note: Due to the nature of Bogobogosort, we will use
-- short tables to perform tests. For higher values of
-- n, we cannot predict the time it will take to perform the
-- sort.

run('Empty arrays', function()
	local t = {}
	assert(same(sort(clone(t)),bogobogosort(t)))
end)

run('Sorted array', function()
	local t = {1, 2, 3, 4, 5}
	assert(same(sort(clone(t)),bogobogosort(t)))
end)

run('Array sorted in reverse', function()
	local t = {5, 4, 3, 2, 1}
	assert(same(sort(clone(t)),bogobogosort(t)))
	local t = {5, 4, 3, 2, 1}
	local comp = function(a,b) return a>b end
	assert(same(sort(clone(t), comp),bogobogosort(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)),bogobogosort(t, comp)))
	local t = {0, 0, 0, 0, 0}
	local comp = function(a,b) return a <= b end
	assert(same(sort(clone(t)),bogobogosort(t, comp)))
end)

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