Bubble Sort Algorithm Explained
In programming, sorting is one of the most common tasks. Among the simplest methods, bubble sort stands out as a basic yet educational example of how comparison-based sorting works. The bubble sort algorithm repeatedly swaps adjacent elements if they are in the wrong order, gradually moving the largest elements toward the end — much like bubbles rising to the surface of water.
Although bubble sort in C or Java is rarely used for large datasets due to inefficiency, it remains a key topic for beginners learning sorting logic, algorithmic thinking, and time complexity analysis.
How Bubble Sort Works
The bubble sort algorithm processes data in multiple passes. In each pass, adjacent elements are compared, and if one is larger than the other, they are swapped. After the first pass, the largest element “bubbles” to the end. After the second pass, the second-largest reaches its correct position, and so on.
If at any point a full pass occurs without any swaps, the algorithm stops — indicating the list is already sorted.
Example
Let’s take an example array:
[64, 34, 25, 12, 22, 11, 90]
Step-by-step explanation:
- Compare the first two numbers: 64 > 34 → swap.
- Compare 64 and 25 → swap again.
- Continue until the largest value (90) reaches the end.
- Repeat the process for the remaining elements until no swaps are needed.
The array transforms through passes like this:
- Pass 1: [34, 25, 12, 22, 11, 64, 90]
- Pass 2: [25, 12, 22, 11, 34, 64, 90]
- Pass 3: [12, 22, 11, 25, 34, 64, 90]
- Pass 4: [12, 11, 22, 25, 34, 64, 90]
- Pass 5: [11, 12, 22, 25, 34, 64, 90]
After the fifth pass, the array is sorted.
Implementation of Bubble Sort in C
Below is a simple implementation of bubble sort in C that includes an optimization — stopping early if no swaps occur during a pass:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;
for (i = 0; i < n – 1; i++) {
swapped = 0;
for (j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf(“Sorted array: “);
for (int i = 0; i < n; i++) printf(“%d “, arr[i]);
return 0;
}
Output:
Sorted array: 11 12 22 25 34 64 90
Bubble Sort in Java
Here’s a similar bubble sort in Java version for educational use:
public class BubbleSortExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n – 1; i++) {
swapped = false;
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.print(“Sorted array: “);
for (int num : arr) System.out.print(num + ” “);
}
}
This version uses a Boolean flag (swapped) to terminate early, saving unnecessary passes on already sorted arrays.
Step Summary Table for Bubble Sort
| Pass | Array State | Largest Element Placed | Swaps Performed |
| 1 | 34 25 12 22 11 64 90 | 90 | 5 |
| 2 | 25 12 22 11 34 64 90 | 64 | 4 |
| 3 | 12 22 11 25 34 64 90 | 34 | 3 |
| 4 | 12 11 22 25 34 64 90 | 25 | 2 |
| 5 | 11 12 22 25 34 64 90 | 12 | 1 |
The process continues until no swaps are needed, confirming the array is sorted.
Time and Space Complexity of Bubble Sort
The bubble sort algorithm is simple but not efficient for large data sets. Its time complexity depends on how sorted the input array is.
| Case | Time Complexity | Explanation |
| Best Case | O(n) | Occurs when the array is already sorted. The optimized algorithm detects no swaps and exits early. |
| Average Case | O(n²) | On average, elements are randomly arranged, leading to multiple passes and swaps. |
| Worst Case | O(n²) | Happens when the array is sorted in reverse order, requiring maximum comparisons and swaps. |
| Space Complexity | O(1) | Uses only a few additional variables for swapping, making it an in-place algorithm. |
Despite being slow, bubble sort is still valuable for demonstrating algorithmic fundamentals like iteration, comparison, and optimization.
Optimizing the Bubble Sort Algorithm
While the core idea is simple, there are a few optimizations that can make bubble sort slightly more efficient:
- Early termination: Stop the algorithm if no swaps occur during a pass.
- Reduced comparisons: After each pass, reduce the number of comparisons since the largest elements are already sorted at the end.
- Bidirectional bubble sort (Cocktail Shaker Sort): Instead of scanning only one direction, alternate passes from left to right and right to left to reduce total passes.
For example, in a nearly sorted dataset, early termination alone can reduce runtime by more than 70%.
Advantages of Bubble Sort
Although inefficient, bubble sort remains one of the most commonly taught algorithms because of its simplicity and transparency.
Key advantages include:
- Easy to implement and understand: Ideal for teaching sorting basics and control structures.
- In-place algorithm: Requires no extra memory apart from temporary variables.
- Stable sorting method: Maintains the relative order of equal elements, which is crucial in applications like database record sorting.
- Detects sorted arrays early: The optimized version can exit after a single pass if no swaps occur.
Disadvantages of Bubble Sort
For real-world applications, however, bubble sort has serious limitations.
- High time complexity: O(n²) makes it impractical for large datasets.
- Inefficient for large-scale systems: Sorting 10,000 elements could require over 50 million comparisons.
- Limited practical usage: Rarely used outside educational or illustrative contexts.
In practice, developers prefer algorithms like Merge Sort, Quick Sort, or Heap Sort for performance-critical applications.
Bubble Sort vs. Other Sorting Algorithms
To understand bubble sort’s place in algorithm design, compare it with more advanced techniques:
| Algorithm | Best Case | Worst Case | Space Complexity | Stability | Real-World Use |
| Bubble Sort | O(n) | O(n²) | O(1) | Stable | Educational examples |
| Insertion Sort | O(n) | O(n²) | O(1) | Stable | Small datasets |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Stable | Large datasets, external sorting |
| Quick Sort | O(n log n) | O(n²) | O(log n) | Unstable | General-purpose, fast |
This comparison shows why bubble sort is rarely used in production but remains important for understanding algorithmic evolution and complexity trade-offs.
When to Use Bubble Sort
While bubble sort in Java or C is inefficient for performance-heavy tasks, it still has learning and testing relevance. You might use it when:
- Teaching algorithmic thinking to students.
- Testing embedded systems with minimal resources.
- Comparing with optimized algorithms for benchmark demonstrations.
A developer might also use bubble sort for very small datasets (less than 10 elements) where simplicity outweighs efficiency.
