Name: Anonymous 2014-01-16 12:05
ITT, we write the final specification and a sample impelementation of the FIBONACCI BUTT SORT
and a sample impelementation
import FIBONACCIBUTTSORT we write the final specificationCould be a good Aprils fools RFC.
function fibonacci_buttsort(list,K,smalli)
local a,b=0,1
local t = {}
if not K then
K=1
end
if not smalli then
smalli=0
end
print("buttsort "..K.." "..smalli)
for i=1,math.huge do
local t2={}
local lastinserted = 0
local needredo = false
local smallest = math.huge
local largest = 0
k=1
while k<=#list do
v=list[k]
if v<=(a/K+smalli) then
if v<smallest then smallest=v end
if v>largest then largest=v end
print("inserted "..v.." a="..a.." a/K+smalli="..a/K+smalli)
table.insert(t2,v)
table.remove(list,k)
k=k-1
if largest>v then --a larger one was inserted first
needredo=true
end
end
k=k+1
end
if needredo then
t2=fibonacci_buttsort(t2, largest-smallest,smallest)
end
table.insert(t,t2)
if #list == 0 then
break
end
a,b=b,a+b
end
local t3 = {}
for i=1,#t do
local t2=t[i]
for j=1,#t2 do
table.insert(t3,t2[j])
end
end
print("end buttsort")
return t3
end
print(table.concat(fibonacci_buttsort({10,2,4,6,13,12,11,23}), ","))
interdasting