Gists Codea Upload

Project.lua

--# Main
-- Sorter

function setup()
    num = 50
    shuffle()
    parameter.integer("num", 10, 800, num)
    parameter.action("new", shuffle)
    --parameter.action("reverse", reverse)
    parameter.action("selection sort", function()
        sort(selection_sort)
    end)
    parameter.action("bubble sort", function()
        sort(bubble_sort)
    end)
    parameter.action("quicksort", function()
        sort(quick_sort)
    end)
    parameter.action("counting sort", function()
        sort(counting_sort)
    end)
    parameter.action("merge sort", function()
        sort(merge_sort)
    end)
end

function shuffle()
    maxv = HEIGHT-10
    data = {}
    for i=1,num do
        data[#data + 1] = math.random(1, maxv)
    end
end

function reverse()
    for i=1,num/2 do
        data[i],data[num+1-i] = data[num+1-i],data[i]
    end
end

function sort(f)
    output.clear()
    print("Sorting ...")
    opc = 0  -- operations count
    sorter = coroutine.create(f)
    coroutine.resume(sorter)
end

function step()
    opc = opc + 1
    if opc % math.floor(num/10) == 0 then
        coroutine.yield()
    end
end

function selection_sort()
    for p=1,num-1 do
        local m,mj = data[p],p
        for i=p+1,num do
            if data[i] < m then
                m = data[i]
                mj = i
            end
            step()
        end
        data[mj],data[p] = data[p],m
    end
end

function bubble_sort()
    for i=1,num-1 do
        for j=1,num-i do
            local x,y = data[j],data[j+1]
            if x > y then
                data[j+1],data[j] = x,y
            end
            step()
        end
    end
end

function quick_sort()
    function quicksort(a, l, r)
        if l < r then
            local j = partition(a, l, r)
            quicksort(a, l, j-1)
            quicksort(a, j+1, r)
        end
    end
    function partition(a, l, r)
        local pivot = a[l]
        local i, j = l, r+1
        while true do
            repeat i = i + 1; step() until (i > r or a[i] > pivot)
            repeat j = j - 1; step() until (a[j] <= pivot)
            if i >= j then break end
            a[i],a[j] = a[j],a[i]
            step()
        end
        a[l],a[j] = a[j],a[l]
        step()
        return j
    end
    quicksort(data, 1, num)
end

function merge_sort()
    local h = {}
    for i=1,num do
        h[i] = 0
    end
    local function merge(a, pf, pl, qf, ql) 
        local i = pf
        local j = qf
        local k = 1
        while i <= pl or j <= ql do
            if i > pl then h[k] = a[j]; j = j + 1 
            elseif j > ql then h[k] = a[i]; i = i + 1
            elseif a[i] <= a[j] then h[k] = a[i]; i = i + 1
            else h[k] = a[j]; j = j + 1 end  
            k = k + 1 
            step()
        end
        k = 1
        for i=pf,pl do
            a[i], k = h[k], k + 1
            step()
        end
        for i=qf,ql do
            a[i], k = h[k], k + 1
            step()
        end
    end
    local function msort(a, first, last)
        if first < last then
            local c = math.floor((first + last)/2)
            msort(a, first, c)
            msort(a, c+1, last)
            merge(a, first, c, c+1, last)
        end
    end
    msort(data, 1, num)
end

function counting_sort()
    local c = {}
    for i=1,maxv do c[i] = 0 end
    for j=1,num do
        c[data[j]] = c[data[j]] + 1
        step()
    end
    for i=2,maxv do
        c[i] = c[i] + c[i-1]
        step()
    end
    local a = data
    data = {}
    for j=num,1,-1 do
        data[c[a[j]]] = a[j]
        c[a[j]] = c[a[j]] - 1
        step()
    end
end

-- This function gets called once every frame
function draw()
    background(40, 40, 50)
    --strokeWidth(0)
    noSmooth()

    -- Draw colored bars representing numbers
    local w = (WIDTH - 10)/num
    strokeWidth(w)
    for i=1,num do
        local v = data[i]
        if v then
            --fill(255*(1-v/maxv),255*(1-math.abs(v/maxv*2-1)),255*v/maxv)
            --rect(5 + (i-1)*w, 5, w-1, v)
            stroke(255*(1-v/maxv),255*(1-math.abs(v/maxv*2-1)),255*v/maxv)
            line(5 + (i-1)*w, 5, 5 + (i-1)*w, 5 + v)
        end
    end
    
    -- animate sort
    if sorter then
        ok,err = coroutine.resume(sorter)
        if not ok and coroutine.status(sorter) == "dead" then
            print("Done. Count = " .. opc)
            sound(SOUND_PICKUP, 37659)
            sorter = nil
        end
    end    
end