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

Discussion in 'Advanced Programming Discussion' started by Lord KJWilliams, Dec 19, 2019.

  1. Lord KJWilliams

    Lord KJWilliams Member

    Joined:
    Jul 2, 2018
    Posts:
    137
    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 :

    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
     
    Desert Dog likes this.
  2. Homunculus

    Homunculus Member

    Joined:
    Jun 20, 2016
    Posts:
    855
    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: Dec 19, 2019
    Lord KJWilliams and IndianaBones like this.
  3. Lord KJWilliams

    Lord KJWilliams Member

    Joined:
    Jul 2, 2018
    Posts:
    137
    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..
     
  4. Homunculus

    Homunculus Member

    Joined:
    Jun 20, 2016
    Posts:
    855
    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: Dec 19, 2019
    Desert Dog likes this.
  5. FrostyCat

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,805
    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.
     
  6. chamaeleon

    chamaeleon Member

    Joined:
    Jun 21, 2016
    Posts:
    1,078
    Yes.
    No.
     
  7. Yal

    Yal GMC Memer GMC Elder

    Joined:
    Jun 20, 2016
    Posts:
    4,178
    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: Dec 21, 2019
  8. chamaeleon

    chamaeleon Member

    Joined:
    Jun 21, 2016
    Posts:
    1,078
     
    Desert Dog and Yal like this.
  9. Desert Dog

    Desert Dog Member

    Joined:
    Jul 30, 2019
    Posts:
    70
    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)

    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.

    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 )

    (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).
     
    Lord KJWilliams likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice