Scripting Helpers is winding down operations and is now read-only. More info→

Sort a table with objects according to their size?

Asked by

KoreanBBQ 301

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.

01for i,v in pairs(checked:GetChildren()) do
02            if v:IsA("BasePart") and v.Name~="Terrain" then
03                for index=1,numParts do
04                    local topHeight=v.Position.Y+0.5*v.Size.Y
05                    local cloneHeight=0
06                    if index~=1 then
07                    cloneHeight=inOrder[index-1].Position.Y+0.5*inOrder[index-1].Size.Y
08                    end
09                    if #inOrder==0 then
10                        inOrder[1]=v
11                        print("life")
12                    elseif topHeight<cloneHeight then
13                        inOrder[index+1]=inOrder[index-1]
14                        inOrder[index-1]=v
15                        for a,b in pairs(inOrder) do
16                            print(b)
17                        end
18                    elseif topHeight>cloneHeight then
19                        inOrder[index+1]=inOrder[index]
20                        inOrder[index]=v
21                    end
22                end
23            end
24        end
 View all 24 lines...

1 answer

Answered by

BlueTaslem 18071

9 years ago

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

1local list = {5, 3, 1, 2, 4}
2table.sort(list)
3print(list[1], list[2], list[3], list[4], list[5])
4-- 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 <:

1function shorter(left, right)
2    return left.Size.y < right.Size.y
3end
4table.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:

1local children = model:GetChildren()
2local parts = {}
3for _, child in pairs(children) do
4    if child:IsA("BasePart") then
5        table.insert(parts, child)
6    end
7end

or by removing non-part elements from the list:

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

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 things¹, 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

01local list = {5, 3, 1, 2, 4}
02local sorted = {}
03while #list > 0 do
04    local mini = 1
05    for i = 2, #list do
06        if list[i] < list[mini] then
07            mini = i
08        end
09    end
10    table.insert(sorted, table.remove(list, mini))
11end

In place implementation (Less memory, faster)

1for i = 1, #list do
2    local minj = i
3    for j = i, #list do
4        if list[j] < list[minj] then
5            minj = j
6        end
7    end
8    list[i], list[minj] = list[minj], list[i]
9end

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

01function quicksort(list)
02    from = from or 1
03    to = to or #list
04    local pivot = list[1] -- ideally this is near the median
05    -- (median of medians or linear time median algorithm should be used)
06    local less = {}
07    local more = {}
08    local same = {}
09    for i = 1, #list do
10        local el = list[i]
11        if el < pivot then
12            table.insert(less)
13        elseif el > pivot then
14            table.insert(more, el)
15        else
16            table.insert(same, el)
17        end
18    end
19    local sorted = {}
20    less = quicksort(less)
21    for i = 1, #less do
22        table.insert(sorted, less[i])
23    end
24    for i = 1, #same do
25        table.insert(soted, same[i])
26    end
27    more = quicksort(more)
28    for i = 1, #more do
29        table.insert(sorted, more[i])
30    end
31    return sorted
32end
 View all 32 lines...

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

Amazingly satisfying answer. I'll test it right away. KoreanBBQ 301 — 9y

Sweet, it worked! KoreanBBQ 301 — 9y