Sorting is one of the most fundamental operations in Computer Science. Whether you’re searching for data, displaying records, or optimizing algorithms, sorting plays a crucial role.
Among all sorting algorithms, Bubble Sort is the simplest and easiest to understand. Although it is not the fastest sorting algorithm, it is an excellent starting point for beginners learning Data Structures and Algorithms (DSA).
In this comprehensive guide, you’ll learn everything about Bubble Sort, including its working principle, algorithm, dry run, Java implementation, time complexity, advantages, disadvantages, interview questions, and much more.
📚 Table of Contents
- What is Sorting?
- What is Bubble Sort?
- Why is it called Bubble Sort?
- Real-Life Analogy
- How Bubble Sort Works
- Step-by-Step Example
- Bubble Sort Algorithm
- Bubble Sort Flow
- Java Program
- Dry Run of the Program
- Time Complexity Analysis
- Space Complexity
- Stable and In-Place Sorting
- Optimized Bubble Sort
- Advantages
- Disadvantages
- Applications
- Bubble Sort vs Selection Sort vs Insertion Sort
- Frequently Asked Questions
- Conclusion
📌 What is Sorting?
Sorting is the process of arranging data in a particular order.
It can be:
- 🔼 Ascending Order (Smallest to Largest)
5 2 9 1 7
↓
1 2 5 7 9
- 🔽 Descending Order (Largest to Smallest)
5 2 9 1 7
↓
9 7 5 2 1
Sorting helps in:
- 🔍 Faster searching
- 📊 Better data analysis
- 💾 Efficient storage
- ⚡ Faster processing
🫧 What is Bubble Sort?
Bubble Sort is the simplest comparison-based sorting algorithm.
It repeatedly compares two adjacent elements and swaps them if they are in the wrong order.
This process continues until the entire array becomes sorted.
👉 The largest unsorted element moves to the end after every pass.
🤔 Why is it Called Bubble Sort?
Imagine air bubbles inside water.
The bubbles rise to the surface one by one.
Similarly,
- The largest element gradually moves toward the end of the array.
- After every pass, one large element reaches its correct position.
Hence the name Bubble Sort.
🫧 Largest elements “bubble up” to the end.
🃏 Real-Life Analogy
Imagine students standing according to their heights.
170 160 180 150
Two adjacent students compare their heights.
If the left student is taller, they exchange places.
This process continues until everyone stands in increasing order.
Exactly the same idea is used in Bubble Sort.
⚙️ How Bubble Sort Works
Bubble Sort repeatedly performs the following steps:
1️⃣ Compare two adjacent elements.
2️⃣ If the left element is greater than the right element, swap them.
3️⃣ Move to the next pair.
4️⃣ Continue until the end of the array.
5️⃣ Repeat the process for the remaining unsorted elements.
✨ Step-by-Step Example
Consider the following array:
[5, 3, 8, 4, 2]
🔹 Pass 1
Compare 5 and 3
5 > 3
Swap
[3, 5, 8, 4, 2]
Compare 5 and 8
No Swap
[3,5,8,4,2]
Compare 8 and 4
Swap
[3,5,4,8,2]
Compare 8 and 2
Swap
[3,5,4,2,8]
✅ Largest element (8) reaches the end.
🔹 Pass 2
Current array
[3,5,4,2,8]
Compare 3 and 5
No Swap
Compare 5 and 4
Swap
[3,4,5,2,8]
Compare 5 and 2
Swap
[3,4,2,5,8]
Now 5 is also fixed.
🔹 Pass 3
[3,4,2,5,8]
Compare 3 and 4
No Swap
Compare 4 and 2
Swap
[3,2,4,5,8]
🔹 Pass 4
[3,2,4,5,8]
Compare 3 and 2
Swap
[2,3,4,5,8]
🎉 Array is now sorted.
📝 Bubble Sort Algorithm
Step 1: Start
Step 2: Compare adjacent elements.
Step 3: Swap if left element is greater.
Step 4: Repeat until the end of the array.
Step 5: Repeat passes until the array becomes sorted.
Step 6: Stop.
🔄 Bubble Sort Flow
Start
↓
Compare Adjacent Elements
↓
Swap if Needed
↓
Move Forward
↓
End of Pass?
↓
Yes
↓
Repeat Next Pass
↓
Array Sorted
↓
Stop
💻 Java Program
public class BubbleSort {
public static void bubbleSort(int arr[]) {
int n = arr.length;
for(int i = 0; i < n - 1; i++) {
for(int j = 0; j < n - 1 - i; j++) {
if(arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] = {5,3,8,4,2};
bubbleSort(arr);
System.out.println("Sorted Array:");
for(int num : arr)
System.out.print(num + " ");
}
}
🖥 Output
Sorted Array
2 3 4 5 8
🔍 Dry Run of the Java Program
Input
[7,4,5,2]
Pass 1
7 4
Swap
4 7 5 2
7 5
Swap
4 5 7 2
7 2
Swap
4 5 2 7
Pass 2
5 2
Swap
4 2 5 7
Pass 3
4 2
Swap
2 4 5 7
Sorted.
📈 Time Complexity Analysis
Let’s calculate the number of comparisons mathematically.
Pass 1
n − 1 comparisons
Pass 2
n − 2 comparisons
Pass 3
n − 3 comparisons
…
Last Pass
1 comparison
Total comparisons:
[
(n-1)+(n-2)+(n-3)+\cdots+1
]
Using the formula:
[
1+2+3+\cdots+k=\frac{k(k+1)}{2}
]
where (k=n-1),
[
\frac{n(n-1)}{2}
]
Ignoring constants and lower-order terms:
[
O(n^2)
]
🔴 Worst Case
Reverse sorted array
5 4 3 2 1
Every comparison results in a swap.
Time Complexity:
O(n²)
🟡 Average Case
Random order array
3 5 1 4 2
Approximately the same number of comparisons are performed.
Time Complexity:
O(n²)
🟢 Best Case (Normal Bubble Sort)
Already sorted array
1 2 3 4 5
Even though no swaps occur, the algorithm still performs all passes because it has no way to know the array is already sorted.
Total comparisons:
[
\frac{n(n-1)}{2}
]
Therefore,
O(n²)
Important: In the standard (non-optimized) Bubble Sort, the best, average, and worst cases are all O(n²).
🚀 Optimized Bubble Sort
We can improve Bubble Sort by introducing a boolean flag named swapped.
- At the beginning of each pass, set
swapped = false. - Whenever a swap occurs, set
swapped = true. - After the pass, if
swappedis stillfalse, stop the algorithm because the array is already sorted.
Optimized Java Code
public static void bubbleSort(int arr[]) {
int n = arr.length;
for(int i = 0; i < n - 1; i++) {
boolean swapped = false;
for(int j = 0; j < n - 1 - i; 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;
}
}
Best Case (Optimized Version)
If the array is already sorted, only one pass is required.
Comparisons:
n - 1
Time Complexity:
O(n)
Average and Worst Cases remain:
O(n²)
💾 Space Complexity
Bubble Sort uses only one temporary variable during swapping.
Therefore,
Space Complexity = O(1)
📌 Is Bubble Sort Stable?
✅ Yes.
Equal elements keep their original relative order after sorting.
Example:
Before
10A 20 10B
After
10A 10B 20
Notice that 10A still appears before 10B.
📌 Is Bubble Sort In-Place?
✅ Yes.
It does not require any extra array.
Only one temporary variable is used.
🌍 Applications of Bubble Sort
Although Bubble Sort is rarely used in production software, it is useful for:
- 🎓 Learning sorting algorithms
- 📚 Teaching Data Structures
- 🧪 Small datasets
- 📝 Academic assignments
- 🎤 Technical interviews (to explain sorting concepts)
📊 Bubble Sort vs Selection Sort vs Insertion Sort
| Feature | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
| Technique | Swap adjacent elements | Select minimum element | Insert element in sorted part |
| Best Case | O(n²) NormalO(n) Optimized | O(n²) | O(n) |
| Average Case | O(n²) | O(n²) | O(n²) |
| Worst Case | O(n²) | O(n²) | O(n²) |
| Stable | ✅ Yes | ❌ No | ✅ Yes |
| In-place | ✅ Yes | ✅ Yes | ✅ Yes |
| Swaps | Many | Few | Shifts instead of many swaps |
❓ Frequently Asked Questions (FAQs)
Q1. Why is it called Bubble Sort?
Because the largest element gradually “bubbles up” to the end of the array after each pass.
Q2. Is Bubble Sort stable?
Yes. Equal elements retain their relative order.
Q3. Is Bubble Sort an in-place algorithm?
Yes. It uses only a constant amount of extra memory.
Q4. What is the best-case time complexity?
- Standard Bubble Sort: O(n²)
- Optimized Bubble Sort: O(n)
Q5. Why is Bubble Sort not preferred for large datasets?
Because it performs a large number of comparisons and swaps, making it much slower than algorithms like Merge Sort or Quick Sort.
Q6. How many passes are required for an array of n elements?
At most n − 1 passes.
Q7. After each pass, which element reaches its correct position?
The largest unsorted element moves to its correct position at the end of the array.
🎯 Key Takeaways
- 🫧 Bubble Sort compares adjacent elements.
- 🔄 It swaps elements that are in the wrong order.
- 📌 After each pass, the largest unsorted element reaches its correct position.
- 📈 Standard Bubble Sort has O(n²) time complexity in the best, average, and worst cases.
- 🚀 The optimized version uses a
swappedflag, reducing the best-case time complexity to O(n). - 💾 It is an in-place sorting algorithm with O(1) extra space.
- ✅ It is a stable sorting algorithm.
- 🎓 It is one of the best algorithms for beginners to understand the fundamentals of sorting.
🎉 Conclusion
Bubble Sort is often the first sorting algorithm introduced in Data Structures because of its simplicity and intuitive working. While it is not suitable for large datasets due to its O(n²) time complexity, it provides an excellent foundation for understanding how sorting algorithms compare and exchange elements.
As you continue your DSA journey, Bubble Sort will help you appreciate why more advanced algorithms such as Merge Sort, Quick Sort, and Heap Sort were developed. Mastering Bubble Sort first makes learning these advanced algorithms much easier.
If you’re just beginning with Java or Data Structures, make sure you understand Bubble Sort thoroughly before moving on to Selection Sort, Insertion Sort, and other advanced sorting techniques.
