Types of searching algorithms

Help and Feedback Scripting Support
#1

What I’m trying to achieve is efficiency in programming. I wouldn’t say I have an issue but need feedback for my piece of mind. Whilst studying for computer science, what came up into my head is using different searching algorithms to maximise how fast you can search through an array. What I thought is that if it’s possible to implement this into ROBLOX but I’m not exactly sure.
This could be different search algorithms such as bubble sort or binary search

Is it possible to use different algorithms and will it be more efficient than using loops(linear search). If so, how?

4 Likes
Optimising "Rendering" system
#2

Bubble sort isn’t strictly a search algorithm, but a binary search is appropriate if your array is in some known order already.

Rather than me writing out some code for a binary search here, you might find it more useful to do a bit of research into how it works and then implement it yourself in Roblox. If you have any trouble, I’ll be happy to help you out!

NB: you’re unlikely to need this kind of thing on a practical basis in a Roblox game.

1 Like
#3

Thanks

#4

Was about to recommend you for this. Didn’t you make a bunch of different sorts in a game?

1 Like
#5

Thanks for reminding me!

@uJordy You might find my collection of visualisations for common algorithms interesting - although there’s nothing on binary search here.

6 Likes
#6

Could you uncopylock the algorithm showcase and / or post the code? Or do you want it to remain closed source?

#7

For now I’d rather keep that place copylocked but I’m happy to explain any of the algorithms there via DMs to anybody who is interested :slight_smile:

1 Like
#8

Thank you again

#9

There are a lot of different ways to go about this; I recommend just looking up lua code for these algorithms. There are already plentiful github resources and websites for algorithms in searching and sorting in Lua. You might even want to consider what kind of data structure you want to use (array, tree, self-balancing tree, etc.).

2 Likes
#10

Yeah I’ll research

#11

There are some algorithms on the wiki.

2 Likes
#12

Yes! You definitely can improve performance with specialized algorithms. You may not be able to implement them as purely as you could in a language with memory pointers like C but a lot is possible with lua tables. By default tables resemble a hash table with their key/value set (which is one of the best data structures for accessing data from large sets quickly).

Read up on creating hash values for keys to answer your question about searching large data sets for a value quickly.

Also related will be Big-O notation. This is a mathematical way of expressing the performance/complexity of different algorithms. A linear search is O(n) because in the worst case it looks through n units. An ideal hash table search would be O(1) because it only needs to look to see if a value exists in 1 spot. Searching a binary tree is O(log(n)) because you are reducing the remaining indexes to search by half on each iteration. Your CS class will get to this soon! :slight_smile:

1 Like
#13

Thank you

1 Like