Wednesday, November 30, 2016

Bubble sort

Sorting, it is a very important skill to have in life. You need to sort your priorities, your choices, what you want, your needs, otherwise, it all becomes a huge mess. You might have heard people say, "You need to have your life sorted out", or, "Wow, he's so young and has his life sorted out". Well, as you can see my good reader, sorting stuff is a very important life skill to have. 

This is true and not just in real life, but in programming stuff as well. Well, stop wondering and read my words, for they are nothing but the truth.
In common programming situations, there comes a time when we need to sort the data we have. Maybe some list you have that you need to sort in some order. Well, how would you do it?
In programming, we have several different algorithms and sorting methods that we can use according to our needs. Today, I'll be introducing one of the most basic ones to you. It is called the bubble sort.
Funny name, right? Well, focus on my words comrade. For now, I shall be imparting knowledge unto you. Enough with the joking around, Let's get right into it now. According to the old saint Wikipedia,
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
So in English, let's assume you have the following list: 2, 5, 3, 1, 9. And you want to sort them using Bubble Sort. What it will do is, compare the first two elements of the list. So, 2 and 5 and see if the first element is larger than second or not. If it's not, then it moves on to the next pair. The second and third element. That are 5 and 3. Now it compares them both and thinks to itself, oh look, 3 is smaller than 5, but it is coming after it. No, wait, that is wrong, I need to fix this. And then it swaps the two numbers with each other. So now the list is..? 2, 3, 5, 1, 9. Now it moves on to the next pair 5 and 1. It again compares them with each other and swaps their places as 1 is smaller than 5. Now for the final elements. 5 and 9. Well, comparing them it sees that hey, they're in the right place. So now your list would be, 2, 3, 1, 5, 9.
Well, it still isn't completely sorted. The number 1 is still not the 1st one. So it runs again, in the same way, pushing 1 to the top and then comparing all the numbers again. So at the end, the list becomes 1, 2, 3, 5, 9.

Pseudocode:

This is the pseudocode used for Bubble sort:

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Why or where use Bubble Sort, though?

Well, good question my child. Bubble sort is a very old technique to sort lists. It may be great for sorting smaller lists like the ones used in the example I gave, but it becomes very time-consuming for larger lists and on a bigger scale. It is good for introducing sorting methodologies to young computer science students, or anyone trying to learn this stuff. Otherwise, it's..well...Meh... So, I'll be discussing more efficient techniques with you quite soon like Insertion Sort and Merge Sort etc. 

If you have any questions, leave them in the comments and I'll be happy to help. 

No comments:

Post a Comment