Is there any application in a game that requires a sorting algorithm such as Bubble Sort?

Is there any use for using sorting algorithms in game programming GML such as Bubble Sort? I have programmed this in C, and I found on only different variations of it. I want to use a sorting algorithm to list in order by id, for making sorting through a ds_map easier. It says on the online manual :

Maps are not sorted in any (recognisable) way, meaning that to find a certain key you may have to iterate through the whole thing (which is very slow).
Has anyone done this using a sorting algorithm such as bubble sort?


Secondly, I looked up the concept of sorting algorithms, and found a website that explains it in C or C++.

Please beware, these pages use advanced subjects in Computer Science.

One page explains the idea of Time Complexity in the use of sorting algorithms , which you might find interesting... see :

https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/

Another page ( same website ) I found on the subject of the sorting algorithm called bubble sort, there is more than one way to implement the use of bubble sort which falls back on the explanation of Time Complexity... see :

https://www.geeksforgeeks.org/analysis-of-different-sorting-techniques/

I have no idea if these sorting techniques will behave the same in GML as they do in C or C++ as shown in the examples.

I want to know a way to cut down the searching in a ds_map, if I am sorting through 1000 entries of a ds_map. The problem is, it says in the online manual there is no order, so a ds_map is NOT contiguous, but is it dynamic like a dynamically linked node list, like in C++ ? No information states that , which I have read in the manual.

Thanks in Advance
 
H

Homunculus

Guest
There may be a use for custom sorting algorithms for sorting arrays or other structures that do not provide a built in way to do that, but there’s no reason to use bubble sort for this instead of more efficient algorithms like quick sort (which of course can be implemented in gml).

Even with a gml implementation of quicksort, it’s easier (and probably faster as well) to just put your values in a ds_grid or a ds_list and sort them using the built in functions, imho.
The same applies to iterating ds_maps, you can simply store all the keys in a ds_list, sort it if you want, and iterate over the keys instead of using the slow ds_map_find_first/next functions.
 
Last edited by a moderator:
There may be a use for custom sorting algorithms for sorting arrays or other structures that do not provide a built in way to do that, but there’s no reason to use bubble sort for this instead of more efficient algorithms like quick sort (which of course can be implemented in gml).

Even with a gml implementation of quicksort, it’s easier (and probably faster as well) to just put your values in a ds_grid or a ds_list and sort them using the built in functions, imho.
The same applies to iterating ds_maps, you can simply store all the keys in a ds_list, sort it if you want, and iterate over the keys instead of using the slow ds_map_find_first/next functions.
So you copy all the keys from the ds_map and store them in a ds_list to make the sorting easy. That makes sense.

I found the explanation for how quick sort is implemented ( same website stated in my OP ) :

https://www.geeksforgeeks.org/quick-sort/

They provide pseudo code listings in the explanation, but they also provide code listings in several other programming languages such as C++, C..
 
H

Homunculus

Guest
You can generate the ds_list from the existing ds_map keys (but that requires to iterate it at least once) or generate the ds_map and ds_list at the same time by adding the key on both sides one at a time. It really depends on the use case, but the end result is the same.

As for the quicksort implementation, you can do it in a recursive way (most common, it's the one proposed in your link), or in an iterative way (https://www.geeksforgeeks.org/iterative-quick-sort/). Game Maker definitely has a depth limit on recursion, which probably depends on the platform you export to, therefore you may consider the latter if you intend to implement and use it in a real game on large datasets. Not sure if that changes anything in terms of speed, the time complexity is the same for both (although the recursive one is probably simpler to implement).
 
Last edited by a moderator:

FrostyCat

Redemption Seeker
I wouldn't bother with bubble sort when there's heap sort available through priority queues (when the maps march in one by one and the sorting key is numeric) and built-in sorting via ds_grid_sort() (when maps have already gathered in a pile), both of which can run at linear-log time.

Implementing sorting algorithms yourself is an academic exercise 99% of the time. In actual practice, you usually reuse a stock solution provided by a language's standard library.
 

Yal

🐧 *penguin noises*
GMC Elder
I had the impression Bubble Sort was an intentionally bad example on how to not implement a sorting algorithm, because of how slow it gets due to redundant operations. The only remotely practical use-case for it I could think of is if you ran an iteration in the background each step to visually sort things (as in, the player is meant to see how things slowly bubble up, which looks more visually appealing than search-sort and is easier to visualize than quicksort), any other sorting algorithm is better. (Except algorithms purposefully made to be ineffective, like Bogosort and the fake quicksort that does everything three times but looks like Quicksort at first glance).

The only cases where you need to implement your own sorting system is if you need to sort by something that can't be turned into a number (e.g. lexiographic sorting with special rules, like W and V being treated as the same letter)... for any other use case, you can add the data you need to a priority queue (arrays are first-order citizens now so you can add as much data as you want) and compute a priority based on which data you want to sort by, then just empty the queue in priority order and put the elements in a ds_list or (preallocated-size) array.

(Note that I use lexiographic sorting of strings as an example because (arbitrary-length) strings can contain more possible values that fits in an int64, so there's no way to map arbitrary strings 1:1 to a standard integer in GM - hashing them loses data so you aren't guaranteed to get a total sort on the hashed data)
 
Last edited:

chamaeleon

Member
The only remotely practical use-case for it I could think of is if you ran an iteration in the background each step to visually sort things (as in, the player is meant to see how things slowly bubble up, which looks more visually appealing than search-sort and is easier to visualize than quicksort)
 
There may be a use for custom sorting algorithms for sorting arrays or other structures that do not provide a built in way to do that, but there’s no reason to use bubble sort for this instead of more efficient algorithms like quick sort (which of course can be implemented in gml).

Even with a gml implementation of quicksort, it’s easier (and probably faster as well) to just put your values in a ds_grid or a ds_list and sort them using the built in functions, imho.
The same applies to iterating ds_maps, you can simply store all the keys in a ds_list, sort it if you want, and iterate over the keys instead of using the slow ds_map_find_first/next functions.
I had some example scripts on the old forum, and a few speed comparisons.

I do recall comparing a quicksort to the built-in ds_sorting, and surprisingly a custom-gml quicksort was slightly faster... in best case scenario. Unfortunately, quicksort does have a worse-case timing, which if it hits it slows right down (about 5-10x slower, I think). If I recall, quicksort does very poorly on sets that are already almost completely sorted.

I remember at the time deciding that (stable) sorting like Heapsorts are the most practical for actual development: Not as 'fast' as quicksort at it's quickest, but it is stable, and doesn't have a worse-case scenario like quicksort that you have to design for.

(And Bubble Sort is just for introducing the concept of sorting, not for live code)

Game Maker definitely has a depth limit on recursion, which probably depends on the platform you export to, therefore you may consider the latter if you intend to implement and use it in a real game on large datasets. Not sure if that changes anything in terms of speed, the time complexity is the same for both (although the recursive one is probably simpler to implement).
Yeah, good advice. With recursion: Some languages are designed for it: If so, knock yourself out. But for GML, stay away from recursion. You can write any recursive function iteratively anyway.

Implementing sorting algorithms yourself is an academic exercise 99% of the time. In actual practice, you usually reuse a stock solution provided by a language's standard library.
Pragmatic, and I'd say generally correct; But is this the case with GML? Also, see example* scenario below.

(Also, where's the fun in that? :p )

Is there any use for using sorting algorithms in game programming GML such as Bubble Sort?
(not Bubble Sort) but sure, of course. Yal's is a good example: for different Lexiographic sorting.

*I haven't done much coding with GML for a long time, but I don't think there's any way to add a custom comparator, right?

So if you had a box of balls, with different shapes and sizes, and you wanted to order them on size "and" shape, you'd write your own comparison function, and then use your own sorting algorithm.
Same for a deck of cards, if you wanted to sort them by suite and value. Etc.

Now: You could assign each of these objects a 'weight', and sort based on that... but that's really not very expressive, and a bit ugly (although probably faster).
 

2DKnights

Member
As mentioned in previous posts Its probably better (and simpler) to use the built-in sorting methods. And sorting a dictionary "ds_map" typically isn't possible as the mappings are associative and also typeless in GML how would you sort {"1" : "a" , 1 : "b" , "01" : c}? As others said you can keep a (list/array/heap) of keys and sort those. That being said, if you wanted to implement your own sorting as an academic exercise, or the built-in sorting doesn't meet your needs, by all means implement your own. Here's where I differ from most of the other postings. If bubble-sort is an algorithm you know then go ahead in and implement that one. Yes people rag on the speed but I'm a bit more pragmatic than that.

Bubblesort's speed becomes an issue as the number of items it needs to sort becomes larger. For example sorting 100 items will on average take about 10000 operations. Other methods like Quicksort might only take about 664 operations. In terms of current hardware both can be processed in milliseconds. Though from a technical perspective Quicksort would be faster in most cases, from a performance perspective it might not be noticeable, and from a implementation perspective Bubblesort might be easier for you to code and understand.



So in the end it really comes down to
  • How many items do you need to sort?
  • How often do you need to sort them?
  • How sorted is the data already?
If you have a lot of data you need to sort, and you need to sort often. (For example sorting a through thousands of items each game frame or two) Then you'll probably need to implement something like a Quicksort.

If you have lots of data you need to sort but you only need to once or twice (for example sorting a few hundred items in an inventory when a user selects "sort") then you can probably get away with a Bubblesort.

If your data is already sorted and you need to add data in place then an insertion sort might be a better choice.


I then decided to test the performance so I ran Bubblesort on 1000 random reals 100 times in GML, and the operation on average took about 104 milliseconds (about 6 frames @ 60 fps) fast enough for most uses. I then ran Bubblesort on 1000 inverse sorted reals 100 times in GML, and the operation on average took about 122 milliseconds still fast enough for most uses.

I guess what I'm saying is don't let efficiency be the only determining factor in the choice of an algorithm, as its important to write code that you'll understand. If the Sorting becomes a bottleneck you can optimize later. Years ago I also read somewhere that the original Final Fantasy 4 used Bubblesort for the Sort command for items, I don't have the reference, and I didn't verify it, but as the inventory was limited to 48 items it seems plausible ;) Happy Coding

I attached my Bubblesort code for interested parties.


 

Attachments

Last edited:
Top