Bubble sort
It is named bubble sort for the way that the smaller or larger elements bubble up to the top. Sometimes it is also known as sinking sort for the opposite reason. It is a comparison sort that repeatedly iterates through the list, compares the adjacent elements and swaps them if they are in the wrong order. This is repeated until the list is sorted.
How does bubble sort work?
Before diving into the working mechanism of bubble sort let’s assume we have an unordered list as [50, 12, 65, -5, 10, -8]. We’ll try to understand how bubble sort works by sorting this list into an ascending ordered list.
We’ll start from the first index. The algorithm will compare the first and second elements. If the first element is greater than the second element, they will be swapped.
Now we’ll compare the second and third elements. If they are in order, nothing will happen. Otherwise, we’ll swap them. This process will be continued until we reach the last element.
As we can see after the first iteration the largest element will be at the end. Now the iteration will start from the beginning again and this will continue until we get an ordered list.
At each iteration, the largest element among the unordered elements is placed in the last position. The iteration continues only in the unordered elements.
So That’s how the bubble sort works. Let’s now jump into the algorithm.
The Bubble Sort Algorithm
The pseudocode of the algorithm can be written as:
There is still scope of optimization of this algorithm a bit. You can find more about bubble sort like optimization, implementation, complexity analysis, applications of bubble sort in the following link.