Greetings my fellow sorcerers and sorceresses!
Today we are gonna talk about a very basic sorting magic called “Bubble Sort”. Bubble sort would probably be the most simple sorting magic ever. Therefore learning it would be very easy. But keep in mind, it is not the most efficient sorting magic out there. I’ll go into details of analysis in another lesson. For now, put on your magic glasses and drink up your study potions and let’s get into understanding how this magic works.
Let’s consider an array of 5 elements.
1 10 9 5 7
Now this is obviously not in any order. Suppose we want to rearrange this array so that it would be in the increasing order. One method to do this can be explained as this.
- Start from the first element (Leftmost Element) and compare it with the second element.
- Since 1 < 10 , order of the first two elements is fine. Therefore, do nothing and move on to the second element
- Compare the second element with the third element.
- Since 10 > 9 , order of this two element is not correct. Therefore, to make it right, these elements need to be swapped.
Now the array would look like this,
1 9 10 5 7
Still we’re not done. So moving on,
- Compare the third element with the fourth element.
- Since 10 > 5 , order of this two element is not correct. Therefore, these elements need to be swapped.
Now the array would look like this.
1 9 5 10 7
As the last two steps,
- Compare the fourth element with the fifth element.
- Since 10 > 7 , order of this two element is not correct. Again same deal, these elements need to be swapped.
Now that we’ve traversed from the beginning to the end of the array. But still it isn’t sorted. Therefore, same steps should be followed again.
1 9 5 7 10
- Compare first and second elements.
- Since 1 < 9, order is right. Therefore, do nothing and move on.
- Compare second and third element.
- Since 9 > 5, order isn’t correct. Therefore swap those elements.
1 5 9 7 10
- Compare third and fourth elements.
- Since 9 > 7, order is wrong. Therefore swap the elements.
1 5 7 9 10
- Compare fourth and fifth elements.
- Since 9 < 10, order is right. Therefore, do nothing.
Hooray! The array is now sorted in the increasing order.
This is basically Bubble sort. You start with the first element and keep on comparing while advancing through the array and do swaps if necessary. You might have to repeat it several times depending on the size of the array and the initial state of the array. In the above example we only had to traverse two times. But this might be not the case for bigger and very disordered arrays.
If you want to order the array in the reverse order, you should start from the last element (Rightmost Element) and traverse to the beginning of the array and swap when the current element is smaller than the compared one.
Before winding up, I want you guys to picture yourself brewing a potion. During the process you can see that all the air bubbles comes up to the surface right? If you think about it, similar thing happens in bubble sort magic too. The maximum element comes up to its right place each time you traverse the array. Its just like an air bubble comes up to the liquids surface. That is the reason behind the name.