32
Bubble Sort
Introduction
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. It is the simplest sorting algorithm.
How does Bubble Sort work?
Suppose we have an array [-2, 45, 0, 11,-9] that we are willing to sort in ascending order.
1. First Iteration or First Pass

2. Remaining Iteration
The same process goes on for the remaining iterations. We will notice that after each iteration, the largest element among the unsorted elements is placed at the end.
In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Algorithm
bubbleSort(array)
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSort
Code Implementation
In Java
package algorithms.sorting;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] nums = {-2, 45, 0, 11,-9};
BubbleSort bs = new BubbleSort();
int swaps = bs.sort(nums);
System.out.println(Arrays.toString(nums));
System.out.println("Total swaps done : " + swaps);
}
public int sort(int[] arr) {
int swaps = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
swaps++;
}
}
}
return swaps;
}
}
In Python
def bubble_sort(array):
swaps = 0
for i in range(len(array)):
for j in range(1, len(array) - i):
if array[j] < array[j - 1]:
temp = array[j]
array[j] = array[j-1]
array[j-1] = temp
swaps += 1
return swaps
if __name__ == '__main__':
nums = [-2, 45, 0, 11, -9]
total_swaps = bubble_sort(nums)
print(nums)
print(f"Total swaps done : {total_swaps}")
Output
[-9, -2, 0, 11, 45]
Total swaps done : 6
Optimized Bubble Sort Algorithm
One thing, we can notice in the above algorithm is that even if the array is already sorted, the comparisons are still done which is useless. This increases the execution time.
To solve this, we can take an extra boolean variable
swapped
or isSwapped
which is set to true if there occurs swapping of elements. Otherwise, it is set false. After an iteration, if there is no swapping, the value of
swapped
or isSwapped
will be false. This means elements are already sorted and there is no need to perform further iterations.This will reduce the execution time and helps to optimize the bubble sort.
Algorithm for Optimized Bubble Sort
bubbleSort(array)
swapped <- false
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
swapped <- true
end bubbleSort
Code Implementation
In Java
package algorithms.sorting;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] nums = {-2, 45, 0, 11,-9};
BubbleSort bs = new BubbleSort();
int swaps = bs.sort(nums);
System.out.println(Arrays.toString(nums));
System.out.println("Total swaps done : " + swaps);
}
public int sort(int[] arr) {
boolean isSwapped;
int swaps = 0;
for (int i = 0; i < arr.length; i++) {
isSwapped = false;
for (int j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
isSwapped = true;
swaps++;
}
}
if (!isSwapped) break;
}
return swaps;
}
}
In Python
def bubble_sort(array):
swaps = 0
for i in range(len(array)):
is_swapped = False
for j in range(1, len(array) - i):
if array[j] < array[j - 1]:
temp = array[j]
array[j] = array[j-1]
array[j-1] = temp
is_swapped = True
swaps += 1
if not is_swapped:
break
return swaps
if __name__ == '__main__':
nums = [-2, 45, 0, 11, -9]
total_swaps = bubble_sort(nums)
print(nums)
print(f"Total swaps done : {total_swaps}")
Output
[-9, -2, 0, 11, 45]
Total swaps done : 6
Bubble Sort Complexity
Time Complexity | |
---|---|
Best | O(n) |
Worst | O(n^2) |
Average | O(n^2) |
Space Complexity | O(1) |
Stability | Yes |
Detailed Complexity
Bubble Sort compares the adjacent elements.
Cycle | Number of Comparisons |
---|---|
1st | (n-1) |
2nd | (n-2) |
3rd | (n-3) |
....... | ...... |
last | 1 |
Hence, the number of comparisons is
(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2
which is nearly equal to n^2
Hence, Complexity: O(n^2)
Time Complexity
O(n^2)
If we want to sort in ascending order and the array is in descending order then the worst case occurs.O(n)
If the array is already sorted, then there is no need for sorting.O(n^2)
It occurs when the elements of the array are in jumbled order (neither ascending nor descending).Space Complexity
O(1)
because an extra variable is used for swapping.O(2)
.Conclusion
In this blog, we discussed the first sorting algorithm - Bubble Sort. This blog post cannot end without thanking the person who has motivated a lot of students to learn DSA, that too free of cost - Kunal Kushwaha and Community Classroom. You can also access his free DSA playlist here.
32