Last Updated on August 29, 2023 by Mayank Dham
Bubble Sort, a fundamental sorting algorithm, embodies the essence of simplicity in programming. It’s a stepping stone for beginners to grasp sorting logic and gain insights into algorithm efficiency. In this article, we delve into the world of Bubble Sort in Python, dissecting its mechanics, implementation, and performance considerations. Whether you’re a coding novice seeking clarity or a programmer looking to refresh your understanding this article will guide you about bubble sort, the bubble sort algorithm in python, and the time and space complexity of the bubble sort program in python.
What is Bubble Sort in Python?
The bubble sort algorithm compares adjacent elements and swaps them to sort the list. The bubble sort uses two for loops to sort the list. The first for loop (outer for loop) is used to traverse the list n times. The Second for loop (inner for loop) is used to traverse the list and swap elements if necessary.
Bubble Sort Algorithm Python:-
Let’s understand how the bubble sort algorithm python works using an example and visualizing the algorithm. The process of sorting the list in ascending using the bubble sort algorithm python is given below.
Now Let’s see how n-1 (n=size of a list) list passes work on a list.
First pass (i=0)
- First, we will run the inner loop for n-i-1 (5-0-1 = 4) times and we will compare each adjacent pair.
- For j=0, compare j=0 (l[0]=4) and j+1=1 (l[1]=3) here l[j]>l[j+1] so we will swap two elements because we want higher elements on the right side to sort a list.
- For j=1, l[1] (4) < l[2] (9) so we will not swap elements because the higher element (9) is already on the right side.
- For j=2, l[2] (9) > l[3] (1) so we will swap elements.
- For j=3, l[3] (9) > l[4] (5) so we will swap elements.
- After performing the first pass we can see that the last element of a list (9) is already at its right position so in further passes we will not touch that element.
Second pass (i=1)
- In the second pass (i=1), we will run inner loop n-i-1 time ( 5-1-1 =3) which one less than the first pass it is because the last element is already sorted in the second pass so we will not consider the last element.
- For j=0, l[0] (3) < l[1] (4) so we will not swap elements.
- For j=1, l[1] (4) > l[2] (1) so we will swap elements.
- For j=2, l[2] (4) < l[3] (5) so we will not swap elements
- After the completion of the second pass, we can see that the last two elements of an list ( [5,9] ) are in their right position.
Third pass (i=2)
- In the third pass ( i=2 ), we will run the inner loop n-i-1 (5-2-1 = 2) times.
- For j=0, l[0] (3) > l[1] (1) so we will swap elements.
- For j=1, l[1] (3) < l[2] (4) so we will not swap elements.
- After performing the third pass we can see that the last three elements ( [4,5,9] ) are in their right positions.
Fourth pass (i=3)
- In the fourth pass (i=3 ), we will run the inner loop n-i-1 (5-3-1=1) times.
- For j=0, l[0] (1) < l[1] (3) so we will not swap elements.
- After performing the fourth pass we can see that our list is sorted.
Sorting happens in place in bubble sort python which means if there are two elements with the same values so after performing the bubble sort program in python the order of that two elements will be the same. Let’s understand this with an example list= [4,6,3,6,5] here two same elements are 6 at index 2 and 4 now after performing bubble sort list= [3,4,5,6,6] now two elements which is same are 6 at index 4 and 5 so element 6 at index 4 is element 6 at index 2 before performing sorting and element 6 at index 5 is the element at index 4 before performing sorting.
Bubble Sort Program in Python:-
def bubble_sort(list1):
for i in range(0,len(list1)-1):
for j in range(len(list1)-1):
if(list1[j]>list1[j+1]):
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp
return list1
list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
print("The sorted list is: ", bubble_sort(list1)) Output
The unsorted list is: [5, 3, 8, 6, 7, 2]
The sorted list is: [2, 3, 5, 6, 7, 8]There is one problem with the above bubble sort program in python when a given list is already sorted the above program will still finish all the two loops so the time complexity becomes O(n^2) though the list is already sorted. Let’s see how can we optimize the above bubble sort program in python.
Optimized Bubble Sort Program in Python:-
We can observe one thing if our list is already sorted then no swap will be performed so we can use this observation to write an optimized bubble sort program in python.
def bubble_sort(list1):
has_swapped = True
while(has_swapped):
has_swapped = False
for i in range(len(list1) - 1):
if list1[i] > list1[i+1]:
# Swap
list1[i], list1[i+1] = list1[i+1], list1[i]
has_swapped = True
return list1
list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
print("The sorted list is: ", bubble_sort(list1)) Time Complexity Analysis of Bubble Sort Python
Best:- O(n) when the given list is already sorted at that time program using only one loop.
Average:- O(n^2) when the given list is not sorted.
Worst:- O(n^2) when the given list is reverse sorted at that time we have to perform a swap for each comparison. So the total swaps performed will be n*(n-1)/2
Auxiliary Space complexity of bubble sort python
Auxiliary space complexity:- O(1) it’s because we are not using any extra list to perform bubble sort python. We are only using variables so the space complexity is O(1) to perform the bubble sort algorithm python.
Conclusion
While Bubble Sort is straightforward and easy to implement, its performance limitations make it impractical for large datasets. Its time complexity of O(n^2) discourages its use for real-world scenarios where efficiency is paramount. However, mastering Bubble Sort’s logic is crucial for understanding sorting algorithms’ basic principles and serves as a foundation for exploring more sophisticated sorting methods. As you advance in your coding journey, you’ll encounter more efficient sorting algorithms that offer better performance for larger datasets.
FAQs Related to Bubble Sort in Python
1. How does Bubble Sort work?
The algorithm repeatedly steps through the list, comparing adjacent elements. If they’re out of order, they’re swapped. This process continues until the entire list is sorted.
2. What is the time complexity of Bubble Sort?
Bubble Sort has a worst-case and average-case time complexity of O(n^2), where n is the number of elements in the list. This makes it inefficient for larger datasets.
3. When should I use Bubble Sort?
Bubble Sort is primarily used for educational purposes and understanding sorting logic. It’s not recommended for real-world applications due to its poor performance with large datasets.
4. Are there more efficient sorting algorithms?
Yes, there are several sorting algorithms that offer better performance than Bubble Sort. Algorithms like Quick Sort, Merge Sort, and Heap Sort have lower time complexities and are preferred for larger datasets.
5. Why is Bubble Sort inefficient?
Bubble Sort compares and swaps elements in a pairwise manner, resulting in many unnecessary swaps. This contributes to its quadratic time complexity.
Other Python Programs
Python program to reverse a number
Python program for heap sort
Python program to check armstrong number
Python program to check leap year
Python program to convert celsius to fahrenheit
Python program to find factorial of a number
Python program to reverse a linked list
Python Program to find the middle of a linked list using only one traversal
Python Program to Add Two Numbers
Python Program to Check Palindrome Number
Python Program to Print the Fibonacci Series
Python Loop Program
Anagram Program in Python