Game maker array sorting algorithms

Discussion in 'Tutorials' started by jazzzar, Aug 28, 2016.

  1. jazzzar

    jazzzar Member

    Joined:
    Jun 29, 2016
    Posts:
    514
    EDIT : NOW SCRIPTS ARE COMMENTED.
    GM Version
    : stable 1.4.1757 Game Maker Studio
    Target Platform: ALL
    Download: Drop Box

    Summary:
    different approches to sort an array using different algorithms

    Hello, so i had some time on my hands yesterday so i decided to write some famous array sorting algorithms, THEY MAY NOT BE beneficial for real game use, these algorithms sort the array in an ascending order, i felt sharing them because they may introduce some of the beginner guys here to understand how to approach things from a different view, they may benefit them to understand programming in general, i tried to make these simple,i followed the same way of how the different algorithms work so yeah...

    Algorithms used :

    • bubble sorting algorithm :
    [​IMG]
    The bubble sort is an algorithm used to sort a sequence of numbers, in our case, it's used to sort an array, but how does it work?

    First, the scales at the right end of the image compares the 2 numbers above it, if the right one is smaller, it gets swapped with the left one, and moves the scales one step to the left,it not, only the scale moves one step and nothing happens with the numbers


    This operation continues to compare the 2 numbers above it and swaps them in the same way as the first two until it reaches the end left of the array,

    Once that position is reached, the number on the leftmost edge is considered fully sorted, in that case, it's the number '1', after that the scales return to the beginning and repeat the process until all the numbers are fully sorted ,

    So the operation occurs array_length_1d(array) times in GML (number of elements in an array in general)
    That's it for the bubble sorting algorithm

    • selection sorting algorithm :
    Selection algorithm is used for the same reason as the one above, but it works differently, let's start with that sequence of numbers :
    [​IMG]
    How the algorithm works is like so, first it does a simple linear search on the numbers to determine the minimum between these :
    [​IMG]
    Once it's determined, the minimum value gets swapped with the leftmost number whatever that last one is, and the minimum value in that case is considered fully swapped :
    [​IMG]
    After that, the leftmost number isn't considered in the linear search anymore, remember it's considered sorted, so the next index for the linear search starts at 1 not 0, so we determine the minimum again of the "new" sequence, once determined, we swap it with the leftmost number at index 1 :
    [​IMG]
    [​IMG]
    So that other minimum is now considered fully sorted and the next search starts at the index 2, that operation continues until all the numbers are fully sorted : [​IMG]
    That algorithm runs the same number of steps as the bubble sort one.

    • insertion sorting algorithm :
    [​IMG]
    The insertion algorithm is somehow harder (not really), but maybe harder for beginner users, it's fairly simple once you get the idea, so how does it work?
    first let's consider that sequence of numbers in the gif,

    First thing that algorithm does is it considers the leftmost number fully sorted, even if it's not, in that case 5 is considered sorted ,

    The next thing it does, is take the next leftmost number of the new sequence which is in our case is 3 ,

    what happens now is the most important thing that makes the algorithm actually work, listen carefully, what it does with that number (3), it simply compares it to left one, which is 5, if it's smaller, 3 goes one step to the left without being swapped unless it finds that the new left number is smaller, or it finds the left edge which is index 0, which is the case for now :

    So what happens is, 5 gets shifted one step to the right, and 3 gets added in 5's place, at index 0, next thing, 4 is taken out, and we start the comparison ,

    4 gets compared with 5, it's smaller, so shift 5 one step to the right, and shift 4 one step to the left(they do not get swapped) ,

    Now, 4 gets compared to 3, it's larger so it sits in it's place (5's old one) ,

    Now, we take the leftmost number which is 7, when we compare it with the number on it's left, we find 7 > 5, nothing happens, and 7 is considered sorted ,

    The operation continues until all the numbers are fully sorted ,

    That algorithm happens array_length_1d(array) - 1, as the first number in the array is always considered sorted, and doesn't have any operations performed at it other than getting shifted.

    I hope this helps someone :)
     
    Last edited: Aug 29, 2016
  2. chance

    chance predictably random Forum Staff Moderator

    Joined:
    Apr 22, 2016
    Posts:
    785
    I suppose this is OK for the Tutorials forum. Writing sorting algorithms is a staple of beginner programming courses. It's a good exercise. And these scripts are OK -- with one script dedicated to each sorting algorithms.

    But I'm not particularly impressed by this example. I think you could do a LOT more to make this useful and instructive for beginners. There's no explanation, no comments. And there's no indication of the performance of each algorithm -- such as number of steps involved, memory usage, speed, whatever.... Your post itself doesn't offer anything beyond Wikipedia links.

    So I'm asking you to do a bit more here. Perhaps you can describe each algorithm briefly. Maybe discuss the performance and CPU overhead of each one.

    And it would be really neat to have an animation showing how each one performs, on a step-by-step basis. That's a fun exercise.
     
    SilentxxBunny and jazzzar like this.
  3. Fodderbot

    Fodderbot Guest

    I'd be interested in seeing an implementation of binary heeps in gamemaker.
     
    jazzzar likes this.
  4. jazzzar

    jazzzar Member

    Joined:
    Jun 29, 2016
    Posts:
    514
    Hey, thanks, indeed it could be more useful, i'm too lazy to explain and make gifs :(, but i'll update today with comments on the code, i'll explain the algorithms instead of the wiki (i'm lazy that's why i used wiki :p) maybe i'll make animated gifs but i'm not sure
    EDIT : post updated with explanations, gmx with scripts commented will be updated soon
    EDIT 2: now scripts are commented, hope that the tutorial is worth it now
     
    Last edited: Aug 29, 2016
    chance likes this.
  5. jazzzar

    jazzzar Member

    Joined:
    Jun 29, 2016
    Posts:
    514
    If i got sometime one day, i'll give this a go, but i don't know how it will benefit someone in anything other than learning purposes, hmmm
     
  6. Mann_mit_Hut

    Mann_mit_Hut Member

    Joined:
    Jun 22, 2016
    Posts:
    80
    Hey, just read the text, these algorithms are the basics in terms of runtime.
    Just missing the merge sort in this class - just for the thrill of it.
    Next thing is the quick sort, one that has a way better runtime on larger arrays.
    And for fun, have a look at random sort ;)
     
  7. jazzzar

    jazzzar Member

    Joined:
    Jun 29, 2016
    Posts:
    514
    Hey, I made this for new people that don't have an understanding of some basic programming things, I don't see where this can be used too, so That's something i'll probably not look into anymore
     
  8. the_dude_abides

    the_dude_abides Member

    Joined:
    Jun 23, 2016
    Posts:
    595
    Wow - Chance's initial reaction to this was somewhat elitest and arrogant "Writing sorting algorithms is a staple of beginner programming courses", and is indicative of some users bad / ignorant attitudes on the community.

    I shall respond with the same slightly obnoxious tone (when in Rome, and all that)

    Consider this fact (and it will blow your mind!) : some people, i.e me and probably many others, don't know how to do these things - because we haven't had "beginner programming courses"....In fact - we haven't had any programming classes at all !!!

    Imagine that! What an absolutely disgusting state of affairs.....and in a first world country too...tsk! tsk!

    There are people who don't know all the things you know.....appallingly stupid intellectual peasants (of course) who don't have the brain capacity to deserve Gamemaker Studio, but because they have the menial capacity to hold a job they can afford to buy it. Regardless of the fact them trying to make a game with it is like a chimp trying to build an atom bomb.

    They are out out there, using their grubby hands and uneducated minds to try and program games.

    And as such, this is useful !! Maybe jazzzar didn't present it particularly well to begin with, and that would be fair enough for Chance to criticize it for those reasons, but I don't think Chance should be judging its value to people.

    Given that they apparently have no concept mere mortals walk the earth, who don't know stuff and appreciate the "chance" to learn things they don't know......

    Rant over!

    I shall finish with a quote by Spongebob Squarepants:
    "Wheeeeeeeeeeee!"
     
    SilentxxBunny likes this.
  9. dewebmeester

    dewebmeester Member

    Joined:
    Apr 28, 2019
    Posts:
    1
    Thanks @jazzzar - Great job. Thanks @the_dude_abides for your comment. Agree. I am a senior developer and teacher at high-school Netherlands and will use this examples in the classroom. So thanks again.
     
  10. SilentxxBunny

    SilentxxBunny Epsilon

    Joined:
    Jun 21, 2016
    Posts:
    62
    First, I want to thank jazzzar for posting this tutorial! Even just the word algorithm gives me a headache. :bash:

    While tone did strike me as passive-aggressive, he has some good points. I trust that he was just trying to offer constructive criticism... but I believe that if you look in the mirror you will see that you have egg on your face. Two wrongs never make a right (although three rights make a left.) We should all try to be nice to each other.

    It's not what you said chance, it's how you said it.

    I shall conclude with a quote from Zelda II - The Adventure of Link: "GET CANDLE IN PARAPA PALACE. GO WEST." This is a lie, it's in the east.

    Edit: I realize that the bulk of my post is about forum drama, and not the tutorial itself. I don't feel good about that. I will edit this post after checking out your tutorial. Again, thank you.
     
    Last edited: Apr 29, 2019

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