Quicksort for ShiVa3D

If you ever need to sort a table of numbers in shiva, I adapted this Rosetta Code entry for shiva.

-- Adapted from http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Lua

function quicksort (t, start, endi)
    
    start = start or 0
    endi = endi or table.getSize ( t ) - 1
    
    if(endi - start < 1) then return t end
    
    local pivot = start
    for i = start + 1, endi do
        if table.getAt ( t, i ) <= table.getAt ( t, pivot ) then
            local temp = table.getAt ( t, pivot + 1 )
            table.setAt ( t, pivot + 1, table.getAt ( t, pivot ) )
            
            if(i == pivot + 1) then
                table.setAt ( t, pivot, temp )
            else
                table.setAt ( t, pivot, table.getAt ( t, i ) )
                table.setAt ( t, i, temp )
            end
            pivot = pivot + 1
        end
    end
    t = quicksort(t, start, pivot - 1)
    return quicksort(t, pivot + 1, endi)
end


The following code:

local tTest = table.newInstance ( )
table.add ( tTest, 1)
table.add ( tTest, 9)
table.add ( tTest, 7)
table.add ( tTest, 3)
table.add ( tTest, 5)
table.add ( tTest, 10)
table.add ( tTest, 6)
table.add ( tTest, -5)
table.add ( tTest, -9)
table.add ( tTest, -15)
table.add ( tTest, 33)
table.add ( tTest, 4)
table.add ( tTest, 8)

this.quicksort (tTest)
for i = 0, table.getSize ( tTest) - 1 do
    log.message ( table.getAt ( tTest, i ) )
end

Produces the output:

-15
-9
-5
1
3
4
5
6
7
8
9
10
33

Be the first to comment

Leave a Reply