Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
2

Sort a table with objects according to their size?

Asked by
KoreanBBQ 301 Moderation Voter
9 years ago

I have a table of object,

I want to sort the objects in a different table, so that newTable[1] is smallest on Y axis, and newTable[#newTable] is the tallest.

I tried using a for loop that manipulates the values but I can't get it right.

for i,v in pairs(checked:GetChildren()) do
            if v:IsA("BasePart") and v.Name~="Terrain" then
                for index=1,numParts do
                    local topHeight=v.Position.Y+0.5*v.Size.Y
                    local cloneHeight=0
                    if index~=1 then
                    cloneHeight=inOrder[index-1].Position.Y+0.5*inOrder[index-1].Size.Y
                    end
                    if #inOrder==0 then
                        inOrder[1]=v
                        print("life")
                    elseif topHeight<cloneHeight then
                        inOrder[index+1]=inOrder[index-1]
                        inOrder[index-1]=v
                        for a,b in pairs(inOrder) do
                            print(b)
                        end
                    elseif topHeight>cloneHeight then
                        inOrder[index+1]=inOrder[index]
                        inOrder[index]=v
                    end
                end
            end
        end

1 answer

Log in to vote
1
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
9 years ago

You can sort a list of things using table.sort:

local list = {5, 3, 1, 2, 4}
table.sort(list)
print(list[1], list[2], list[3], list[4], list[5])
-- 1 2 3 4 5

This sorts by comparing elements using <. You can't compare parts using this, of course. That's why table.sort has an optional second parameter which is your own function to replace <:

function shorter(left, right)
    return left.Size.y < right.Size.y
end
table.sort(parts, shorter)

That will do what you want if parts is a list of parts.

Filtering for only parts

If model is a model that contains parts and some other objects, it would probably be best to filter the other objects out. You can either do that by constructing a new table:

local children = model:GetChildren()
local parts = {}
for _, child in pairs(children) do
    if child:IsA("BasePart") then
        table.insert(parts, child)
    end
end

or by removing non-part elements from the list:

local parts = model:GetChildren()
for i = #parts, 1, -1 do
    -- note that it doesn't work going forward
    -- (can you figure out why? There are questions on SH about this already)
    if not child:IsA("BasePart") then
        table.remove(parts, i)
    end
end

Implementing Sorting

It looks like you were trying to implement a sort yourself. In general, this is a bad idea, because it's going to be more confusing and slower than the built-in implementation. Still, it's a interesting problem that is taught in intro CS.

Here's a few ways to sort things1, but just using < to compare (replace a < b with less(a, b) for custom comparisons)

Selection Sort

IDEA: First thing is smallest. Second thing is smallest (other than the smallest one). Third thing is smallest (other than the 2 smallest). Etc.

Performance: Very slow, always.

Copying implementation

local list = {5, 3, 1, 2, 4}
local sorted = {}
while #list > 0 do
    local mini = 1
    for i = 2, #list do
        if list[i] < list[mini] then
            mini = i
        end
    end
    table.insert(sorted, table.remove(list, mini))
end

In place implementation (Less memory, faster)

for i = 1, #list do
    local minj = i
    for j = i, #list do
        if list[j] < list[minj] then
            minj = j
        end
    end
    list[i], list[minj] = list[minj], list[i]
end

Bubble Sort

IDEA: Move bigger things up one step at a time.

Performance: Very slow, almost always. Sometimes very fast. No extra memory usage.

TODO

Merge Sort

IDEA: Be stupid, and unable to sort lists of more than 2 elements (which we can do because of <). Sort pieces of lists and put them together.

Performance: Fast, always. Requires a lot of extra memory.

Quicksort

IDEA: Pick an element. All the elements less than it can be sorted in their own pile. All the element more than it can be sorted in their own pile.

Performance: Fast, but only usually. No extra memory usage (needed).

Copying implementation -- wastes memory

function quicksort(list)
    from = from or 1
    to = to or #list
    local pivot = list[1] -- ideally this is near the median
    -- (median of medians or linear time median algorithm should be used)
    local less = {}
    local more = {}
    local same = {}
    for i = 1, #list do
        local el = list[i]
        if el < pivot then
            table.insert(less)
        elseif el > pivot then
            table.insert(more, el)
        else
            table.insert(same, el)
        end
    end
    local sorted = {}
    less = quicksort(less)
    for i = 1, #less do
        table.insert(sorted, less[i])
    end
    for i = 1, #same do
        table.insert(soted, same[i])
    end
    more = quicksort(more)
    for i = 1, #more do
        table.insert(sorted, more[i])
    end
    return sorted
end

  1. I'm sorry, I totally got carried away. I haven't done this in Lua before 

0
Amazingly satisfying answer. I'll test it right away. KoreanBBQ 301 — 9y
0
Sweet, it worked! KoreanBBQ 301 — 9y
Ad

Answer this question