Bubble Sort
Definition
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list of numbers, compares adjacent numbers, and swaps them if they are in the wrong order. This process continues until the list is sorted. The largest unsorted element "bubbles up" to its correct position after each pass through the list.
Just like the movement of air bubbles in the water that rise to the surface, each maximum array element moves to the end in each iteration. Therefore, it is called a bubble sort.
Let us understand a step-by-step working of bubble
sort with an example :
Suppose we have the following array of integers nums: [64, 34, 25, 10, 22, 11, 90] that we want to sort in ascending order:
Step-by-Step Working
Pass 1
- Compare 64 and 34: 64 > 34, so swap them.
- nums: [34, 64, 25, 10, 22, 11, 90]
- Compare 64 and 25: 64 > 25, so swap them.
- nums: [34, 25, 64, 10, 22, 11, 90]
- Compare 64 and 10: 64 > 10, so swap them.
- nums: [34, 25, 10, 64, 22, 11, 90]
- Compare 64 and 22: 64 > 22, so swap them.
- nums: [34, 25, 10, 22, 64, 11, 90]
- Compare 64 and 11: 64 > 11, so swap them.
- nums: [34, 25, 10, 22, 11, 64, 90]
- Compare 64 and 90: 64 < 90, so no swap.
- nums: [34, 25, 10, 22, 11, 64, 90]
After Pass 1, the largest number (90) is in its correct position. We can say that 90 is bubbled to the end of the array.
Pass 2
Pass 2:
array nums before pass 2: [34, 25, 10, 22, 11, 64, 90]
- Compare 34 and 25: 34 > 25, so swap them.
- nums: [25, 34, 10, 22, 11, 64, 90]
- Compare 34 and 10: 34 > 10, so swap them.
- nums: [25, 10, 34, 22, 11, 64, 90]
- Compare 34 and 22: 34 > 22, so swap them.
- nums: [25, 10, 22, 34, 11, 64, 90]
- Compare 34 and 11: 34 > 11, so swap them.
- nums: [25, 10, 22, 11, 34, 64, 90]
- Compare 34 and 64: 34 < 64, so no swap.
- nums: [25, 10, 22, 11, 34, 64, 90]
After Pass 2, the second largest number (64) is in its correct position. We can say that 64 is bubbled up.
Pass 3
Pass 3:
array nums before pass 3: [25, 10, 22, 11, 34, 64, 90]
- Compare 25 and 10: 25 > 10, so swap them.
- nums: [10, 25, 22, 11, 34, 64, 90]
- Compare 25 and 22: 25 > 22, so swap them.
- nums: [10, 22, 25, 11, 34, 64, 90]
- Compare 25 and 11: 25 > 11, so swap them.
- nums: [10, 22, 11, 25, 34, 64, 90]
- Compare 25 and 34: 25 < 34, so no swap.
- nums: [10, 22, 11, 25, 34, 64, 90]
After Pass 3, the third largest number (34) is in its correct position. We can say that 34 is bubbled up.
Pass 4
Pass 4:
array nums before pass 4: [10, 22, 11, 25, 34, 64, 90]
- Compare 10 and 22: 10 < 22, so no swap.
- nums: [10, 22, 11, 25, 34, 64, 90]
- Compare 22 and 11: 22 > 11, so swap them.
- nums: [10, 11, 22, 25, 34, 64, 90]
- Compare 22 and 25: 22 < 25, so no swap.
- nums: [10, 11, 22, 25, 34, 64, 90]
After Pass 4, the fourth largest number (25) is in its correct position. We can say that 25 is bubbled up.
Pass 5
Pass 5:
array nums before pass 5: [10, 11, 22, 25, 34, 64, 90]
- Compare 10 and 11: 10 < 11, so no swap.
- nums: [10, 11, 22, 25, 34, 64, 90]
After Pass 5, the fifth largest number (22) is in its correct position.
Pass 6
Pass 6:
array nums before pass 6: [10, 11, 22, 25, 34, 64, 90]
- Compare 10 and 11: 10 < 11, so no swap.
- nums: [10, 11, 22, 25, 34, 64, 90]
Do we need any more passes?
We have already done 6 passes, which means 6 out of 7 elements are at the right places. Imagine there are 10 seats in a bus and 10 passengers. 9 took their right seat, so automatically the last person would get the right seat without even searching for it. Since the n-1 elements are in their correct position then the remaining element will automatically go to the correct position. Therefore the array becomes sorted.
Final Sorted nums: [11, 12, 22, 25, 34, 64, 90]
Let us understand it through animations
Here is the Brute Force code of bubble sort in all languages
Brute Code in All Languages
C++ Code Try on Compiler!
class Solution
{
public:
void bubbleSort(vector<int> &nums)
{
int n=nums.size();
for (int i = 0; i < n; i++)
{
// Initialize the swapped flag
bool swapped = false;
// Traverse the vector from the start to the end minus i
for (int j = 0; j < n - i - 1; j++)
{
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
if (nums[j] > nums[j + 1])
{
// Swap if they are in the wrong order
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
// Set the swapped flag to True
swapped = true;
}
}
// If no elements were swapped, the vector is sorted
if (!swapped)
{
break;
}
}
}
};
Java Code Try on Compiler!
class Solution {
void bubbleSort(int[] nums) {
// Get the number of elements in the array
int n = nums.length;
// Outer loop denoting each pass (total passes required is n-1)
for (int i = 0; i < n; i++) {
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
for (int j = 0; j < n - i - 1; j++) {
// Compare the adjacent elements
if (nums[j] > nums[j + 1]) {
// Swap if they are in the wrong order
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
Python Code Try on Compiler!
class Solution:
def bubbleSort(self, nums):
n = len(nums)
# Outer loop denoting each pass (total passes required is n-1)
for i in range(n):
# Inner loop traverses up to the unsorted portion of the array
# as the last i elements are already sorted in their correct
# position
for j in range(0, n - i - 1):
# Compare the adjacent elements
if nums[j] > nums[j + 1]:
# Swap if they are in the wrong order
nums[j], nums[j + 1] = nums[j + 1], nums[j]
Javascript Code Try on Compiler!
// Class for the Bubble Sort solution
class Solution {
bubbleSort(nums) {
let n = nums.length;
// Outer loop denoting each pass (total passes required is n-1)
for (let i = 0; i < n; i++) {
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
for (let j = 0; j < n - i - 1; j++) {
// Compare the adjacent elements
if (nums[j] > nums[j + 1]) {
// Swap if they are in the wrong order
let temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
Can we optimize the steps of this algorithm?
Yes, you can see in the step-by-step working process above that the array becomes sorted by Pass 4.
However, we still performed 2 extra passes (Passes 5 and 6) to complete the sorting.
Could we optimize this, Can we keep track of the array after each iteration to check whether it is already sorted?
Yes, you can determine that your array is completely sorted when, during a pass, no swaps are needed between adjacent elements based on the comparison.
In this given example, we can see that in Pass 4, swaps are required and the fourth-largest number is correctly placed, but we are not sure if the entire array is sorted yet.
However, in Pass 5, no swaps are needed, which means the array is
already sorted.
Therefore, running the remaining passes, where no swaps will be required, is unnecessary.
So to check whether an array is fully sorted, we need to use a boolean variable swapped initialized with false that monitors if swaps are taking place in a particular pass.
If swaps are taking place then we turn our swapped to true, else we keep our swapped variable as it is.
If no swaps are taking place during a pass, it means the swapped remains false. We can check if the swapped is still false and break the loop, as this indicates that the array is already sorted.
Let's understand it through visuals
Here is the code for the optimized bubble sort in all languages
Optimised Code in All Languages
C++ Code Try on Compiler!
class Solution
{
public:
void bubbleSort(vector<int> &nums,int n)
{
for (int i = 0; i < n; i++)
{
// Initialize the swapped flag
bool swapped = false;
// Traverse the vector from the start to the end minus i
for (int j = 0; j < n - i - 1; j++)
{
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
if (nums[j] > nums[j + 1])
{
// Swap if they are in the wrong order
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
// Set the swapped flag to True
swapped = true;
}
}
// If no elements were swapped, the vector is sorted
if (!swapped)
{
break;
}
}
}
};
Java Code Try on Compiler!
class Solution {
public void bubbleSort(int[] nums) {
// Get the number of elements in the array
int n = nums.length;
for (int i = 0; i < n; i++) {
// Initialize the swapped flag
boolean swapped = false;
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
for (int j = 0; j < n - i - 1; j++) {
// Compare the adjacent elements
if (nums[j] > nums[j + 1]) {
// Swap if they are in the wrong order
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
swapped = true; // Set the swapped flag to True
}
}
// If no elements were swapped, the array is sorted
if (!swapped) {
break;
}
}
}
}Python Code Try on Compiler!
class Solution:
def bubbleSort(self, nums):
n = len(nums)
for i in range(n):
# Initialize the swapped flag
swapped = False
# Inner loop traverses up to the unsorted portion of the array
# as the last i elements are already sorted in their correct
# position
for j in range(0, n - i - 1):
# Compare the adjacent elements
if nums[j] > nums[j + 1]:
# Swap if they are in the wrong order
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# Set the swapped flag to True
swapped = True
# If no elements were swapped, the list is sorted
if not swapped:
break
Javascript Code Try on Compiler
class Solution {
bubbleSort(nums) {
let n = nums.length;
for (let i = 0; i < n; i++) {
// Initialize the swapped flag
let swapped = false;
/* Inner loop traverses up to the unsorted portion of the array
as the last i elements are already sorted in their correct
position */
for (let j = 0; j < n - i - 1; j++) {
// Compare the adjacent elements
if (nums[j] > nums[j + 1]) {
// Swap if they are in the wrong order
let temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
// Set the swapped flag to true
swapped = true;
}
}
// If no elements were swapped, the array is sorted
if (!swapped) {
break;
}
}
}
}
Time Complexity
Worst Case : O(n²)
The worst case occurs when the array is sorted in reverse order.
Number of Comparisons: In Bubble Sort, for each pass through the array, adjacent elements are compared. For an array with n elements, you need to make approximately n−1 comparisons in the first pass, n−2 in the second pass, and so on.
- First Pass: n−1 comparisons
- Second Pass: n−2 comparisons
- Third Pass: n−3 comparisons
- ...
- Last Pass: 1 comparison
Total Comparisons: The total number of comparisons made is the sum of the first n−1 natural numbers, which is given by the formula: (n*(n-1))/2.Simplifying, this results in approximately (n*(n-1))/2, which is O(n²).
Number of Swaps: Each comparison may require a swap if the elements are out of order. Since Bubble Sort requires a swap for each out-of-order comparison, the number of swaps is also proportional to the number of comparisons.
Overall Time Complexity: Because both the number of comparisons and swaps are proportional to (n*(n-1))/2, the overall time complexity in the worst case is O(n²).
Average Case : O(n²)
In the average case for bubble sort, where elements are in random order, the algorithm still performs O(n²) operations.
This is because, on average, each element needs to be compared with and potentially swapped with adjacent elements across multiple passes through the array. Although better than the worst case (reverse order), the average case complexity remains O(n²) due to the quadratic number of comparisons and swaps required.
Best Case : O(n)
Best Case:
The best case occurs when the array is already sorted. In this situation, bubble sort can be optimized by recognizing that no swaps are needed and terminating early. However, the classic version of bubble sort does not always include this optimization and would still perform n−1 passes through the array, resulting in O(n²) time complexity for the unoptimized version.
The optimized version can achieve O(n) by adding a flag to detect if any swaps were made during a pass.
Space Complexity
Bubble Sort has a constant space complexity of O(1). It only requires a small, fixed amount of extra space for the swapping of elements, loop counters (i and j), and the boolean variable swapped used for optimization, regardless of the size of the input array.
Thus, Bubble Sort is considered an in-place sorting algorithm, meaning it sorts the array without needing extra space proportional to the number of elements.
Stability of Algorithm
Yes, Bubble Sort is a stable sorting algorithm.
This means that it maintains the relative order of equal elements. If two elements are equal, they will remain in the same relative order in the sorted array as they were in the original array.
Application of Bubble Sort
It can be used effectively for small lists or arrays where its quadratic time complexity does not pose a significant performance issue.
This can be useful in specific scenarios where simplicity is preferred over efficiency.