Quicksort - open source native Lua implementation of Quicksort

Resources Community Resources
, , ,
#1

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).

Detailed description

Compared to all other sorting algorithms, quicksort has the fastest and most reliable time complexity of (in the best case) O(n log n). In the worst-case quicksort has a time complexity of O(n) (which is still faster than most sorting algorithms)!

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 - https://www.roblox.com/library/6129195525/Quicksort-Module

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.

I made a GitHub with the source code and license if anyone wants to take a look at that (Under the incense of which you agree not to redistribute this module under your own name)!

9 Likes
#3

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

10 Likes
#4

Oh yeah sorry about that. I found that out only after I created the module and everything :sweat_smile:.

The difference between my method and theirs though is that my method comes with more customizability.

If you wanted, you could go into the module and try to change the pivot point for peak optimization. Or you could go in and change some other things to teak the module how you would like.

Another thing is that when sorting a table using my module, you can include a second argument set to true to sort the table from greatest to least.

I was hoping that people would comment ideas for things that I would be able to add into the module to make it more useful.

1 Like
#5

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.

2 Likes
#6

2 things -

  1. Unfortunately, that may be true, but most of that performance loss could be made back by putting the entire script onto 1 line. Interpreters run scripts line by line, so putting it all on the same line would make it almost equally as fast as a compiler (though it would be a lot messier).

  2. I already completely understand that this module IS NOT necessary. I made this module because I felt like open-sourcing an interesting piece of code that I thought could help somebody. I would appreciate it if, instead of pummeling my module, you could give me feedback on ways to make it useful.

1 Like
#7

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
#8

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
#9

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

#10

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

1 Like