jazzzar
Member
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 :
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
How the algorithm works is like so, first it does a simple linear search on the numbers to determine the minimum between these :
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 :
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 :
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 :
That algorithm runs the same number of steps as the bubble sort one.
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
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 :
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 :
How the algorithm works is like so, first it does a simple linear search on the numbers to determine the minimum between these :
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 :
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 :
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 :
That algorithm runs the same number of steps as the bubble sort one.
- insertion sorting algorithm :
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: