A Bubble sort is an easy algorithm among the various sorting algorithms. We learn it as a first sorting algorithm. It is easy to learn and highly intuitive. It can be easy to implement into the code, which is much beneficial for beginner software developers. But it is the worst algorithm for sorting the elements in every except because it checks every time the array is sorted or not.
Let's understand the concepts of the bubble sort.
Concept of Bubble Sort
The bubble sort uses a straightforward logic that works by repeating swapping the adjacent elements if they are not in the right order. It compares one pair at a time and swaps if the first element is greater than the second element; otherwise, move further to the next pair of elements for comparison.
Example -
We are creating a list of element, which stores the integer numbers
list1 = [5, 3, 8, 6, 7, 2]
Here the algorithm sort the elements -
First iteration
It compares the first two elements and here 5>3 then swap with each other. Now we get new list is -
[3, 5, 8, 6, 7, 2]
In second comparison, 5 < 8 then swapping happen -
[3, 5, 8, 6, 7, 2]
In third comparison, 8>6 then swap -
[3, 5, 6, 8, 7, 2]
In fourth comparison, 8>7 then swap -
[3, 5, 6, 7, 8, 2]
In fifth comparison, 8>2 then swap-
[3, 5, 6, 7, 2, 8]
Here the first iteration is complete and we get the largest element at the end. Now we need to the len(list1) - 1
Second Iteration
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 2, 7, 8] here 7>2 then swap their position. Now
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 2, 7, 8] here 7<8 then no swap taken place.
Third Iteration
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 6<2 then swap their positions
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 6<7 then no swap taken place. Now
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 7<8 then swap their position.
It will iterate until the list is sorted.
Fourth Iteration -
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8]
[3, 5, 2, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
Fifth Iteration
Check the each element and as we can see that our list is sorted using the bubble sort technique.
Implementation in Python Code
We have already described the technique of bubble sort. Now, we will implement the logic in the Python code.
Program
Output:
Explanation:
In the above code, we have defined a bubble_sort() function which takes list1 as an argument.
Without using a temp variable
We can also swap the elements without using the temp variable. Python has a very unique syntax. We can use the following lines of code.
Example -
Output:
Optimization of Python Code Implementation
We can optimize the above code using the two techniques. The swaps are not done; it means list is sorted. In the previous technique - The previous technique will evaluate the complete list though it doesn't seem necessary to do.
We can prevent the unnecessary evaluation using the Boolean flag and checks if any swaps were made in the previous section.
Example -
Output:
In the second technique, we consider the fact that the iteration is ended when the largest element of the list end up at the end of the list.
The first time, we pass the largest element at the end position using the n position. The second time, we pass through the n-1 position, the second largest element.
In each consecutive iteration, we can compare at one less element than before. More accurately, in the k-th iteration, only need to compare at the first n - k + 1 elements:
Example -
Output:
Time Comparison
Let's see the time comparison between the above code snippets.
Unoptimized Bubble Sort Takes: 0.0106407
Optimize Bubble Sort Takes: 0.0078251
Bubble Sort with a Boolean flag and shortened list Takes: 0.0075207
All techniques are useful for the fewer elements, but if the list consists of many elements, then the second optimize technique make a huge difference.
need an explanation for this answer? contact us directly to get an explanation for this answer