LÖVE

Code: Select all

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */ 
  lu_byte lsizenode;  /* log2 of size of `node' array */
  struct Table *metatable;
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  GCObject *gclist;
  TValue *array;  /* array part */
  int sizearray;  /* size of 'array' array */
} Table;

Code: Select all

math.randomseed(os.time())
Bucket = {}
mt = {}
function Bucket:new()
	return setmetatable({size=0,data={}},mt)
end
function Bucket:push_front(val)
	table.insert(self.data,0,val)
	self.size = self.size + 1
end
function Bucket:pop_back()
	self.size = self.size - 1
end
function Bucket:back()
	return self.data[self.size-1]
end
mt.__index = function(t,key)
				if type(key) == "number" then
					return t.data[key]
				else
					return Bucket[key]
				end
			 end
mt.__newindex = function(t,key,value)
					error(key.." is not a part of class Bucket")
				end

local function L2GRadixSort(SL)
	local Buckets = {Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new(),Bucket:new()}
	Buckets[0] = Bucket:new()
	local Size = SL.size
	local Bucket_0_Size=0
	local i=0,x
	while not (Bucket_0_Size == Size) do
		for j=0,Size-1,1 do
			Buckets[math.floor((SL[j]/(10^i))%10)]:push_front(SL[j])
		end
		Bucket_0_Size = Buckets[0].size
		x = 0
		for j=0,9,1 do
			local Bucket_Size = Buckets[j].size
			for k=0,Bucket_Size-1,1 do
				SL[x] = Buckets[j]:back()
				x=x+1
				Buckets[j]:pop_back()
			end
		end
		i=i+1
	end
end

local UnSorted = {}
UnSorted.size = 0
for i=0,100000,1 do
	UnSorted[i] = math.random(100)
	UnSorted.size = UnSorted.size + 1
end
local start = os.time()
L2GRadixSort(UnSorted)
local finish = os.time()
print(finish-start)
--[[for i=1,UnSorted.size-1,1 do
	print(UnSorted[i])
end]]
os.execute("pause>nul")

Code: Select all

function L2GRadixSort(SL) {
	local Size = SL.len();
	local Buckets = array(256,null);
	foreach(i,val in Buckets) {
		Buckets[i] = [];
	}
	local BucketSize;
	local Bucket_0_Size = 0;
	local j=0,k=0,i=0,x=0;
	for(;Bucket_0_Size!=Size;++i) {
		j=0;
		do {
			Buckets[(SL[j]>>(i*8))%256].push(SL[j]);
			++j;
		} while(j<Size);
		Bucket_0_Size = Buckets[0].len();
		j=0;
		x=0;
		do {
			BucketSize = Buckets[j].len();
			for(k=0;k<BucketSize;++k) {
				SL[x++] = Buckets[j][0];
				Buckets[j].remove(0);
			}
		} while(++j<256);
	}
}

function gen_random(seed,max) {
	local last=seed
	local IM = 139968;
	local IA = 3877;
	local IC = 29573;
	for(;;) {  //loops forever
		yield (max * (last = (last * IA + IC) % IM) / IM);
	}
}
local randtor = gen_random(42,1000000);
local test = [];
test.resize(100000);
for(local i=0;i<100000;++i) {
	local x = resume randtor;
	test[i] = (x<0)?(-x):(x);
}
print("\n");

L2GRadixSort(test);

for(local i=0;i<10;++i) {
	print(test[i]+"\n");
}