Coding Journal

What is the bubble sort algorithm?

The Bubble Sort Algorithm is one of the ways to sort an array in order. 
It is a very inefficient method, but as I've just started learning classic algorithms, I feel really excited that I managed to understand it and implemented in not only on a simple array of numbers.

So how it works? 

We have an unordered list of numbers [2, 1, 5, 4]. 
We want to put the numbers from the smallest to the biggest one. 
To do it we will be comparing every two numbers, and if the first number is bigger than the second one we have to swap them, and then the second number we will compare with the third one and so on until the end of the array. 
But this is not the end of the checking. We have to repeat checking and swapping until it won't be any swapping in every round. 

My example is very simple (and it is my first time using a diagram editor ) but to understand more complex examples, it's good to watch the gif from Wikipedia

https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif

How to implement it in Python code?

Steps:

1. We can create a function called bubble_sort that has got one argument - a list of numbers.
2. Then we need two additional variables. The end_index which is equal to the length of our array minus one and the sorted variable that has got a value of False.
3. Then we have to create a while loop that works as long as sorted is not True. 
4. We can accidentally make the while loop working forever so in the next line we declare sorted to be True
5. Next, we are going through for loop that is in the range of end_index. 
6.  In this for loop, we will be checking if the previous element is bigger than the next item. 
7. If the element is bigger instead of smaller, we have to declare sorted once again to False, 
8. and swap elements. 
9. When all pairs are sorted and sorted is True the while loop will be over, and we will have to return our arr in a new order 

Of course, parts after # are comments to help to visualize how the code works. 

At the beginning, I wrote that the bubble sort algorithm is highly ineffective. It is because the more elements are there in the list, the more loops it has to do to check numbers against each other. 
If we add a counter variable to our function, we can see how the number grows exponentially with the length of an array. 

working code: https://repl.it/@maknetaRo1/TrivialKnowingFact

This is the very basic implementation of the Bubble Sort Algorithm.  Next time I will explain how I used this algorithm to sort a list of words. 

Bibliography:

Wikipedia artilce: https://en.wikipedia.org/wiki/Bubble_sort