Suggestions on how to make this sorting code faster

Help and Feedback Scripting Support
#21

When it comes to sorting you’re probably not going to be able to implement an algorithm that is faster than the default table.sort(). The more interesting question is why are you sorting? Can you just keep the result and use that for subsequent lookups? Can you sort once and keep the order when elements are added? Can you instead use a hash table? Can you reduce the amount of elements that need sorting? Can you scrap sorting altogether and process each thing in an arbitrary order? Is it fine if it takes a while and you yield during the sort?

All of these depend on the problem sorting is solving. But when it comes to sorting itself, you’re probably not going to see a massively better algorithm than table.sort()

#22

numerical loops runs about 30% faster than next loop and pairs loop according to this website

i saw you using next loop so i had to mention it because the first thing that came to my mind is that you used a next loop because its faster than a pairs loop but it might be a wrong assumption that came out of the blue

#23

i have a better suggestion than my last one. the last one was kind of basic

basically to make this piece of code run faster, the problem is that what this code is doing is

note: randomNumbersTable being folder:GetChildren() in this case
1: take a random number from the randomNumbersTable
2: compare the random number to every number in the randomNumbersTable
3: index into tableOfSizes once complete
4: repeat

do you not see the problem?

the question is that, do you REALLY have to compare one number to every number to achieve this?

is it really that necessary?

and the answer is that there is a better way to go about it compared to how you went about it then to make this code run faster, you’ll have to change the approach and get rid of the thought of comparing one number to every other number.

note: orderedTable is tableOfSizes
i suggest you try this method i came up with:
take a random number from the randomNumbersTable.
blindly index into orderedTable.
ask the computer “is the random number indexed smaller than the random number indexed before it”.
if the random number indexed IS smaller than the random number indexed before it then keep swapping the index of the most recent random number indexed with the index before it until the index before it has a number smaller than it.
repeat.

--also i scripted it for you
local callsMade = 0

local random = Random.new()

local randomNumbers = {}

for i = 1, 250 do
	randomNumbers[i] = random:NextInteger(1, 41019238712983712)
end

local numbersMinToMax = {}
numbersMinToMax[0] = -math.huge

local function sort(i, randomNumber)
	callsMade += 1
	numbersMinToMax[i] = randomNumber
	
	if randomNumber < numbersMinToMax[i - 1] then
		numbersMinToMax[i] = numbersMinToMax[i - 1]		
		sort(i - 1, randomNumber)
	end

end

local theTimeWhenThisVarWasMade = os.clock()

for i = 1, #randomNumbers do
	callsMade += 1
	sort(i, randomNumbers[i])
end

local speedPerformance = os.clock() - theTimeWhenThisVarWasMade

print(numbersMinToMax)
print(callsMade)
print(speedPerformance)

note: this method can be made theoretically faster if it has a guessing mechanical that makes a better guess out of a bad one and keep repeating it until it reaches the correct index but you should just use table.sort. The point of this was to prove that there is a better way to go about “compare the random number to all numbers in the table”

summary of suggestion: just dont repeat “compare the random number to all numbers in the table” because this is the MAIN reason why your code is slow

#24

Roblox uses Luau, not native Lua and there’s a lot of internal changes. I would advise you to do all the benchmarking yourself if you want a clear answer
The screenshot below is from a benchmark back in 2021
image