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
- Starting with index zero, compare the first and second elements.
- If the first element is greater than the second element, swap them.
- Compare the second and third elements, and swap them if the second element is greater than the third element.
- Repeat the above process till the last element
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
-
Worst Case Complexity:
O(n^2)If we want to sort in ascending order and the array is in descending order then the worst case occurs. -
Best Case Complexity:
O(n)If the array is already sorted, then there is no need for sorting. -
Average Case Complexity:
O(n^2)It occurs when the elements of the array are in jumbled order (neither ascending nor descending).
Space Complexity
- Space complexity is
O(1)because an extra variable is used for swapping. - In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be
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.
Image Courtesy: Programiz
Visualize algorithms easily on visualgo.net.
Top comments (0)