Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Bubble Sort, Quick sort, and swap sort

edited October 2013 in Code Sharing Posts: 6

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
</code>
<code>
    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.

Tagged:

Comments

  • Posts: 2,820

    Nice job. I'll try it out later. By the way, when posting code on the forums, use ~~~ before and after the code to format it propperly.

  • Posts: 6

    Ok, thanks zoyt, will do next time

Sign In or Register to comment.