Sorting is the technique of arranging data in any particular form, like in ascending or descending order. We have many techniques to sort data but bubble sort in python is one of the easiest. In Python Bubble Sort, swapping takes place between the adjacent elements (elements which are directly left or right) if they are not in the correct order.
Python Bubble sort can be used wherever simplicity is required, but speed can be compromised. It uses very little space when compared to other sorting techniques.
Concept used in Bubble Sort
The concept used behind bubble sort is explained below with an example.
Suppose we have a list of 5 elements ‘list1’ and we wan to sort the list in ascending order( smallest to largest).
list1=[7,5,9,6,3]
PASS-1
7 5 9 6 3 -> 5 7 9 6 3 (swapped because 7>5) 5 7 9 6 3 -> 5 7 9 6 3 (not swapped because 7<9) 5 7 9 6 3 -> 5 7 6 9 3 (swapped because 9>6) 5 7 6 9 3 -> 5 7 6 3 9 (swapped because 9>3)
We have found the largest element ‘9’ and it will not be involved in further iterations( we can say 9’ )
PASS-2
5 7 6 3 9 -> 5 7 6 3 9 (not swapped because 5<7) 5 7 6 3 9 -> 5 6 7 3 9 (swapped because 7>6) 5 6 7 3 9 -> 5 6 3 7 9 (swapped because 3>7)
We have found the second largest element ‘7’ and it will also be fixed.
PASS-3
5 6 3 7 9 -> 5 6 3 7 9 (not swapped because 5<7) 5 6 3 7 9 -> 5 3 6 7 9 (swapped because 6>3)
We have found the third largest element ‘6’ and it will also be fixed.
PASS-4
5 3 6 7 9 -> 3 5 6 7 9 (swapped because 5<3)
We finally got the sorted list.
Observations
We have successfully applied bubble sort on list1 and the following observations can be made from it.
- The number of total passes is equal to 4 for a list with 5 elements. Therefore, it can be concluded that n-1 passes are required for sorting a list using bubble sort.
- The number of iterations per pass is decreasing by 1. For Pass-1 we have 4 iterations. For Pass-2 we have 3 iterations and it goes on till 1 iteration is left. Therefore, number of iterations- n-1, n-2, — n/n.
Implementation of Bubble sort in python:
For sorting in ascending order:
# Python Bubble Sort program
def bubble_sort(list1):
for i in range(0,len(list1)-1): # The total number of passes,bubbles: i
for j in range(0,len(list1)-i-1): # The total number of iterations: j
if list1[j] > list1[j+1]:
list1[j],list1[j+1]=list1[j+1],list1[j] # swap elements
return list1
list1=[7, 5, 9, 6, 3]
print(bubble_sort(list1))
OUTPUT-
[3,5,6,7,9]
The python bubble sort also works on list of strings the same way.
list1=['bhavya','sonu','ashwini','zubair','dheeraj' ]
print(bubble_sort(list1))
On giving the above list the function returns output as follows:
['ashwini', 'bhavya', 'dheeraj', 'sonu', 'zubair']
For sorting in Descending order-
def bubble_sort_descending(list1):
for i in range(0,len(list1)-1):
for j in range(0,len(list1)-i-1):
if list1[j] < list1[j+1]:# Observe '<' is used instead of '>'
list1[j],list1[j+1]=list1[j+1],list1[j]
return list1
list1=[7, 5, 9, 6, 3]
print(bubble_sort_descending (list1))
OUTPUT-
[9, 7, 6, 5, 3]
Pass- 1 [7, 5, 9, 6, 3] [7, 5, 9, 6, 3] [7, 9, 5, 6, 3] [7, 9, 6, 5, 3] Pass- 2 [7, 9, 6, 5, 3] [9, 7, 6, 5, 3] [9, 7, 6, 5, 3] Pass- 3 [9, 7, 6, 5, 3] [9, 7, 6, 5, 3] Pass- 4 [9, 7, 6, 5, 3]
We can observe that we got the correct output 2nd Pass Iteration-2 but still our algorithm keeps on sorting the already sorted list. This is one of the shortcomings of bubble sort. This problem can be solved using insertion or any other sorting algorithm. For a better understanding of Insertion sort visit https://www.pythonpool.com/insertion-sort-python/
Insertion Sort In-depth Tutorial Video
Advantages of Bubble Sort
- Simplest Algorithm for sorting.
- As the sorting takes on the same list(commonly known as in-place sorting) it takes less space. Space Complexity = O(1).
- Generally used in understanding the basics of sorting.
- If the data is very small it can outperform some of the best sorting algorithms like quicksort as they do complex calculations on the data and takes more time and space.
Limitations of python bubble sort
- As we observed above, even if the list gets sorted the algorithm keeps sorting the list till (n-1)th pass. Despite having the same time complexity as insertion and other sorting technique it is slower.
- Due to so many passes and iterations, it takes a lot of time. Also, as in the program for loop is used inside another for loop it has a time complexity of O(n^2).
Conclusion
Out of all sorting techniques, python bubble sort is one of the simplest sorting techniques and great for getting started, but cannot be used for large data due to its large time complexity.
Try to run the programs on your side and let me know if you have any queries.
Happy Coding!