Quicksort - open source native Lua implementation of Quicksort

Hello! I’ve recently created a quicksort module that is able to order arrays incredibly fast and I would like to open source it. I know this may sound useless, but hear me out.

For this reason, I created my quicksort module. This module uses an algorithm known as quicksort to sort number arrays as fast as computationally and physically possible (Please refer below for more info).

This module currently only has 2 built-in functions, but I will be adding more down the line.

  1. module.sortArray(array) - Set an array to this function and the array will be sorted.
  2. module.printTable(table) - Prints all the entries inside of a table.

While yes, the built-in table-sort function may already use quick sort, my module comes with some advantages.

  1. Customizability
  2. Open-source

Here is a link to the Roblox model if you’re interested - Quicksort Module - Roblox

I haven’t figured out a way to use tick() to measure my module’s true speed, but if anyone could figure out how to do so, please let me know! (And no, quicksort cannot yet sort tables containing strings).

Feel free to contribute to the project by leaving suggestions here on this post or messaging me.

10 Likes

In the source code for Lua 5.1 there’s a comment that specifies it uses quicksort.

https://www.lua.org/source/5.1/ltablib.c.html

12 Likes

Since default lua table functions are created in C, they will always run faster than a custom remake of the function, since C is a compiled language and compiled languages are known to run faster than interpreted ones such as lua / luau. Just to add on to Autterfly.

3 Likes

Interpreters run scripts line by line, so putting it all on the same line would make it almost equally as fast as a compiler

This is false. Lua is compiled to bytecode instructions, which is then executed by the interpreter. Removing whitespace does not make your script run any faster.

4 Likes

I wrote a quick test for it and found that in sorting arrays 10,000 arrays it was consistently averages about .5E-9 to 1.0E-9 seconds slower than table.sort.

Here is the source code if you want to learn how to make your own tests


local QuickSort = require(script.quicksortModule);


local QuickSortTime = 0;
local LuaSortTime = 0;

for i = 1,10 do
	for i = 1,10000 do
		local Table1 = {};
		local Table2 = {};

		for i = 1,100 do
			Table1[i] = math.random(-100,100);
			Table2[i] = Table1[i];
		end

		local Start = tick();
		QuickSort.sortArray(Table1);
		QuickSortTime = tick() - Start;

		Start = tick();
		table.sort(Table2);
		LuaSortTime = tick() - Start;

		if i % 500 == 0 then
			wait();
		end
	end
	print("Test run #"..tostring(i))
	print(QuickSortTime/10000);
	print(LuaSortTime/10000);
	print();
end 

as for

I would appreciate it if, instead of pummeling my module

When you create a module with Faster sorting method for arrays in the title under the community resource, it is implied that this is a thing that should be used by other developers, this is not something that should be used by any programmer seeking faster sorting. If you had posted it as “an open source native Lua implementation of QuickSort” then it would be a fine thing for other people to reference when experimenting and trying their hand at writing sorting algorithms. However you posted it as a tool to be used by everyone over a built in Lua function and as a more experienced developer he was informing any young programmer who might run into this thread in the future, that this is not actually faster.

7 Likes

Thank you all for the feedback, I will edit this post accordingly.

I think performance measurements are done using os.clock() and not tick().

1 Like