recently for a speech on algorithms, I utilized Codea to demonstrate the efficiency of the various sort algorithms. I thought I would post up the code to help anyone doing a similar demonstration. This code sorts random lists utilizing various methods and outputs the result to the screen after each iteration. Sorry about the lack of comments:
function table.copy(t)
local t2 = {}
for k,v in pairs(t) do
t2[k] = v
end
return t2
end
function sort(A)
local itemCount=#A
local hasChanged
repeat
hasChanged = false
itemCount=itemCount - 1
for i = 1, itemCount do
if A[i] > A[i + 1] then
A[i], A[i + 1] = A[i + 1], A[i]
hasChanged = true
end
end
until hasChanged == false
end
function randomize(thing,itemCount)
i=1
for i=1, itemCount do
thing[i]=math.random(0,HEIGHT)
end
end
function bs()
mode="b"
randomize(list,itemCount)
end
function qs()
mode="q"
randomize(list,itemCount)
piv = 1
k=1
pivot = 1
end
function ss()
mode="s"
randomize(list,itemCount)
begin=1
end
function ss2()
mode="s2"
randomize(list,itemCount)
begin=#list
end
function reverse()
i=0
local beg=#list
`
`
while beg>0 do
selectionSort2(list, beg)
beg = beg - 1
end
begin=1
piv=1
k=1
pivot=1
end
function order()
sort(list)
begin=1
piv=1
k=1
pivot=1
end
function setup()
begin=1
mode="b"
print("Hello World!")
len=100
x = os.clock()
list = { }
randomize(list,100)
piv = 1
k=1
itemCount=#list
pivot = 1
parameter.action("bubble sort", bs)
parameter.action("quick sort", qs)
parameter.action("swap sort", ss)
parameter.action("ordered", order)
parameter.action("reverse", reverse)
end
function bubbleSort(A)
local itemCount=#A
local hasChanged
hasChanged = false
itemCount=itemCount - 1
for i = 1, itemCount do
if A[i] > A[i + 1] then
A[i], A[i + 1] = A[i + 1], A[i]
hasChanged = true
end
end
if(hasChanged==false) then
background(0, 19, 255, 255)
end
end
function quicksortin(t,p,i)
if t[i] <= t[p] then
local temp = t[p + 1]
t[p + 1] = t[p]
if(i == p + 1) then
t[p] = temp
else
t[p] = t[i]
t[i] = temp
end
end
return p + 1
end
function selectionSort(t,start)
local size=#t
if(start<size) then
local least =t[start]
local leasti = start
local i=0
for i=start, size do
if(t[i]<least) then
least=t[i]
leasti=i
end
end
local thisVal=t[start]
t[start]=least
t[leasti]=thisVal
else
background(0, 19, 255, 255)
end
end
function selectionSort2(t,stop)
local size=#t
if(stop>0) then
local least =t[stop]
local leasti = stop
local i=0
for i=1, stop do
if(t[i]<least) then
least=t[i]
leasti=i
end
end
local thisVal=t[stop]
t[stop]=least
t[leasti]=thisVal
else
background(0, 19, 255, 255)
end
end
function quicksort(t, start, endi)
start, endi = start or 1, endi or #t
if(piv==pivot) then
end
if(endi - start < 0) then
return t
end
local pivot = start
local i=0
for i = start + 1, endi do
pivot=quicksortin(t,pivot,i)
end
piv=pivot
return quicksort(t, pivot + 1, endi)
end
function wait(seconds)
x=os.clock()
repeat
-- used to wait secconds
until os.clock() - x>seconds
end
function draw()
background(40, 40, 50)
strokeWidth(5)
local listCopy=table.copy(list)
local isSorted=true
sort(listCopy)
for i = 1, #listCopy do
local j=listCopy[i]
if(list[i]==j) then
else
isSorted=false
end
end
if(mode=="b") then
bubbleSort(list)
end
if(mode=="q") then
list=quicksort(list)
if(isSorted) then
background(0, 19, 255, 255)
end
end
if(mode=="s") then
selectionSort(list, begin)
begin = begin + 1
end
if(mode=="s2") then
selectionSort2(list, begin)
begin = begin - 1
end
for i, j in pairs(list) do
rect(WIDTH/#list*i,0,WIDTH/#list,j)
end
wait(.1)
end
P.s. For whatever reason, the bubble sort and quick sort appear the same.