Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
✓ ANSWER ACCEPTED

Sort a table with objects according to their size?

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

✓ Accepted answer

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 things[^1], but just using < to compare (replace a < b with less(a, b) for custom comparisons)

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

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

2 comments

0

Amazingly satisfying answer. I'll test it right away.

0

Sweet, it worked!

This discussion is preserved as it was. New answers, comments, and votes are closed.