Bubble Sort Algorithm
Today, I’m gonna discuss Bubble Sort Algorithm. Like Insertion Sort Algorithm, bubble sort is another important sorting algorithm in Data Structures that always comes up in interviews and once you understand it fully you can easily implement it in your favourite programming language such as Python, C++ or Java.
Let’s get started.
In the bubble sort algorithm, we scan the array from left to right.
Suppose we have an array of integers. Our task is to sort the given array in increasing order. Those items which are out of order we swap them.
8, 2, 4, 1, 3
Compare the first two integers at index 0 and 1. If the right item is smaller than the left one, we will swap them and the resulting array is:
2, 8, 4, 1, 3
Now, compare the items at index 1 and 2. Again look at the right integer. If it is smaller than the left integer swap them with each other.
The resulting array is:
2, 4, 8, 1, 3
Then do the same procedure again and again unless 8 reaches its final position.
2, 4, 1, 8, 3
Then,
2, 4, 1, 3, 8
So, integer 8 is in its correct position. We don’t need to swap 8 again.
In this way, our first iteration is completed. We need multiple iterations or passes to fully sort this array. After each pass, the next largest item bubbles up and moves to its correct position.
Now start the next iteration. First, you need to compare the first two items which are 2 and 4. In this case, 4 is larger so you do not need to move it. Then compare 4 with 1. As 4 is larger than 1 so swap it with 1 like this.
2, 1, 4, 3, 8
Now, compare 4 with 3 and swap each other.
2, 1, 3, 4, 8
So, we see that 4 is now in its correct location and we don’t need to swap it further.
In the final step, we need to compare the first two integers 2 and 1 and swap them and you see the array is fully sorted.
1, 2, 3, 4, 8
We don’t need to swap 3 as it is already in its correct location. By swapping these numbers we have now our final array.
1, 2, 3, 4, 8
Time Complexity
In the best-case scenario, the array is already sorted.
For the best-case scenario Time Complexity is 0(n), Linear.
In the worst-case scenario, the array is sorted in reverse order.
For the worst-case scenario Time Complexity is 0(n²), Quadratic.
Reference for this article:
