When I want to sort something in a table to least to greatest, or the contrary, my code looks like this:
as an example if I wanted to sort these trees with different sizes thats in a folder in workspace in a table,
local tableOfSizes = {}
for _, v in next, folder:GetChildren() do
local size = 0
for _, v in next, folder:GetChildren() do
if v.Size >= size and not table.find(tableOfSizes, v.Size) then
size = v.Size
end
end
table.insert(size)
end
the code above sorts every size greatest to least. However, sometimes there are just so much things in a folder that this becomes extremely inefficient, after all, if you have 30 items in a folder and you wanted to sort through it with that code, it you would be doing a total of 30*30, or 30^2 iterations. I have a folder with 250 items so it was a total of 250^2 iterations, so the player had a lag spike when ever I did this code. If you can, please leave some tips or suggest some sorting methods that you use as well.
can you elaborate on why putting it in a dictionary-like format makes it run faster?
there is also one issue on this, when you assign a key value pair in a dictionary it won’t be in the same order as you placed it in. That is why im using both dictionaries and tables so I can simply run through a table thats in the right order that has the name of all the keys in the dictionary and then reference the key to get the value in each iteration.
The intention is not to replace the table itself with this; but rather use it as a supplement–a “blacklist” table that efficiently records the values that have already been stored in tableOfSizes.
It’s not faster, table.sort() is the meta for sorting on roblox
local tableTest : Array<number> = {}
local randomNumber : number
--Filling the table with 100 random numbers to sort
for i = 1, 100 do
randomNumber = math.random(1, 1000)
table.insert(tableTest, randomNumber)
end
print(tableTest) --Unsorted table
table.sort(tableTest, function(a : number, b : number)
return a > b
end)
print(tableTest) --Sorted table
local array, hash = {}, {}
for i = 1, 1e3 do
table.insert(array, i)
hash[i] = true
end
return {
ParameterGenerator = function()
return
end;
Functions = {
["array"] = function(Profiler)
for i = 1, 1e3 do
if table.find(array, i) then
local a = i
end
end
end;
["hash"] = function(Profiler)
for i = 1, 1e3 do
if hash[i] then
local a = i
end
end
end;
};
}
On a google search, table.sort uses quicksort, which has on average O(n log n) complexity, the best complexity you can have in a sorting algorithm. There’s also probably a quicksort/mergesort/heapsort implementation in Lua somewhere online.
Not to mention, OP is using two nested for loops and table.find, which I think averages out to O(n^3) complexity. It could at least be simplified to selection sort, which is O(n^2).
Edit: I double-checked the Luau source code, and it uses the quicksort algorithm as well as vanilla Lua.
Read the title. “Suggestions on how to make this sorting code faster”. I am making a suggestion on making his code faster. He is using table.find to which I am suggesting a faster alternative.
Yes, I was wrong, I remember reading from some source a while back that said table.sort used a linear sorting algorithm
And just a clarification, a hash map has nothing to do with sorting, it’s about his code itself where he used table.findas part of his sorting algorithm
local function swap(arr, i, j)
local temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
end
local function partition(arr, left, right)
local pivot = arr[right]
local i = left - 1
for j = left, right - 1 do
if arr[j] < pivot then
i += 1
swap(arr, i, j)
end
end
swap(arr, i + 1, right)
return i + 1
end
local function quickSort(arr, left, right)
if left >= right then
return
else
local pivot = partition(arr, left, right)
quickSort(arr, left, pivot - 1)
quickSort(arr, pivot + 1, right)
end
end
return {
ParameterGenerator = function()
local tableTest : Array<number> = {}
local randomNumber : number
--Filling the table with 100 random numbers to sort
for _ = 1, 100 do
randomNumber = math.random(1, 1000)
table.insert(tableTest, randomNumber)
end
return tableTest
end,
Functions = {
["table.sort"] = function(Profiler, tableTest : Array<number>)
table.sort(tableTest, function(a, b)
return a > b
end)
end,
["Insertion Sort"] = function(Profiler, tableTest : Array<number>)
for start = 2, #tableTest do
local temp = tableTest[start]
local index = start
while index > 1 and temp < tableTest[index - 1] do
tableTest[index] = tableTest[index - 1]
index = index - 1
end
tableTest[index] = temp
end
end,
["Quick Sort"] = function(Profiler, tableTest : Array<number>)
quickSort(tableTest, 1, 2)
end,
}
}
local tableOfSizes = {}
for _, v in ipairs(folder:GetChildren()) do
table.insert(tableOfSizes, {instance = v, size = v.Size})
end
table.sort(tableOfSizes, function(a,b)
return a.size > b.size -- or a.size < b.size (whichever order you need)
end)
for _, sortedItem in ipairs(tableOfSizes) do
warn(sortedItem.instance, sortedItem.size)
--sortedItem would be of type: {instance: any, size: number}
end
