Definition
- Bubble sort – a simple comparison-based algorithm that steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order.
- Bubbling – after each full pass, the largest remaining element has drifted to its correct position at the end.
- Early exit – a
swappedflag stops the algorithm if a pass completes with no swaps, making it O(n) on sorted input. - Stability – equal elements are never swapped past each other, so their original order is preserved.
- Quadratic – O(n^2) in the worst and average cases, making it unsuitable for large data.
Imagine the National Bank of India arranging a row of account balances written on cards. The clerk compares the first two cards; if the left one is bigger, she swaps them. Then she compares the second and third, swapping if needed, and keeps moving right. After one full sweep, the largest balance has drifted all the way to the far right, like a bubble rising to the top. She repeats the sweeps until the whole row is sorted.
Understanding the Concepts
What is bubble sort?
Bubble sort is the simplest comparison-based sorting algorithm. It steps through the array comparing each pair of adjacent elements and swaps them if they are in the wrong order. After each complete pass, the largest unsorted element has "bubbled" to its correct position at the end.
package com.bank.sort;
import java.math.BigDecimal;
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(BigDecimal[] 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].compareTo(arr[j + 1]) > 0) {
BigDecimal temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // already sorted
}
}
public static void main(String[] args) {
BigDecimal[] balances = {
new BigDecimal("75000"),
new BigDecimal("25000"),
new BigDecimal("50000"),
new BigDecimal("10000"),
new BigDecimal("90000")
};
bubbleSort(balances);
System.out.println("Sorted: " + Arrays.toString(balances));
}
}
Sorted: [10000, 25000, 50000, 75000, 90000]
How does each pass work?
The outer loop counts passes. The inner loop walks adjacent pairs, comparing and swapping. After pass one, the biggest element is at the end. After pass two, the second biggest is in place. The inner loop shrinks by one each time because the tail is already sorted.
package com.bank.sort;
public class BubbleSortTrace {
public static void bubbleSortTrace(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;
}
}
System.out.println("Pass " + (i + 1) + ": " + java.util.Arrays.toString(arr));
if (!swapped) { System.out.println("No swaps, done early!"); break; }
}
}
public static void main(String[] args) {
int[] amounts = {50, 20, 40, 10, 30};
bubbleSortTrace(amounts);
}
}
Pass 1: [20, 40, 10, 30, 50]
Pass 2: [20, 10, 30, 40, 50]
Pass 3: [10, 20, 30, 40, 50]
Pass 4: [10, 20, 30, 40, 50]
No swaps, done early!
Why is the swapped flag important?
Without the swapped flag, bubble sort always performs the full n^2 work even if the array is already sorted. The flag checks whether any swap happened during a pass. If no swaps occurred, the array is sorted and the algorithm can exit early. This makes bubble sort O(n) on already-sorted or nearly-sorted input.
package com.bank.sort;
public class EarlyExit {
public static void main(String[] args) {
int[] sorted = {10, 20, 30, 40, 50};
int passes = 0;
int n = sorted.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (sorted[j] > sorted[j + 1]) {
int tmp = sorted[j]; sorted[j] = sorted[j+1]; sorted[j+1] = tmp;
swapped = true;
}
}
passes++;
if (!swapped) break;
}
System.out.println("Passes on sorted input: " + passes); // just 1
}
}
Passes on sorted input: 1
Why is bubble sort stable?
Bubble sort is stable because it only swaps adjacent elements when the left one is strictly greater than the right one. Equal elements are never swapped past each other, so their original relative order is preserved.
package com.bank.sort;
public class StabilityDemo {
public static void main(String[] args) {
// Two transactions with same amount 50000
String[] ids = {"T1", "T2", "T3"};
int[] amounts = {50000, 50000, 30000};
// Bubble sort by amount
for (int i = 0; i < amounts.length - 1; i++) {
for (int j = 0; j < amounts.length - 1 - i; j++) {
if (amounts[j] > amounts[j + 1]) {
int ta = amounts[j]; amounts[j] = amounts[j+1]; amounts[j+1] = ta;
String ts = ids[j]; ids[j] = ids[j+1]; ids[j+1] = ts;
}
}
}
// T1 still before T2 (both 50000): stable!
for (int i = 0; i < ids.length; i++) {
System.out.println(ids[i] + ": " + amounts[i]);
}
}
}
T3: 30000
T1: 50000
T2: 50000
What is the time and space complexity?
| Case | Time | Reason |
|---|---|---|
| Best | O(n) | Already sorted, one pass, no swaps |
| Average | O(n^2) | Random order |
| Worst | O(n^2) | Reverse sorted |
| Space | O(1) | In-place, only temp variable |
package com.bank.sort;
public class BubbleComplexity {
public static void main(String[] args) {
int[] sizes = {100, 1000, 10000};
for (int n : sizes) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = n - i; // worst case: reversed
long start = System.nanoTime();
bubbleSort(arr);
long ms = (System.nanoTime() - start) / 1_000_000;
System.out.println("n=" + n + " time=" + ms + "ms");
}
}
static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
}
}
n=100 time=0ms
n=1000 time=3ms
n=10000 time=150ms
How is bubble sort different from selection sort?
| Feature | Bubble Sort | Selection Sort |
|---|---|---|
| Mechanism | Swap adjacent pairs | Find minimum, swap to front |
| Swaps per pass | Many (every adjacent pair) | Exactly one |
| Stable | Yes | No (basic version) |
| Early exit | Yes (swapped flag) | No (always scans fully) |
| Best on | Nearly sorted data | Write-minimising scenarios |
When should you use bubble sort?
Never in production. Bubble sort's O(n^2) time makes it hopeless for large datasets. It is valuable as a teaching tool because it is the clearest illustration of comparison and swapping. In real banking code at the National Bank of India, always use Collections.sort or Arrays.sort.
package com.bank.sort;
import java.util.Arrays;
public class ProductionVsBubble {
public static void main(String[] args) {
int n = 100_000;
int[] data = new int[n];
for (int i = 0; i < n; i++) data[i] = (int)(Math.random() * 1_000_000);
int[] copy = data.clone();
long start = System.nanoTime();
Arrays.sort(copy);
System.out.println("Arrays.sort: " + (System.nanoTime()-start)/1_000_000 + "ms");
// Bubble sort on 100K would take minutes: do not attempt.
System.out.println("Bubble sort on 100K: too slow to demonstrate.");
}
}
Arrays.sort: 8ms
Bubble sort on 100K: too slow to demonstrate.
What are common mistakes?
The most common mistake is forgetting the swapped flag, which makes bubble sort always do the full quadratic work. Another mistake is not shrinking the inner loop by i, which means already-sorted tail elements are re-examined on every pass.
package com.bank.sort;
public class BubbleMistake {
// WRONG: inner loop does not shrink
static void buggy(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1; j++) { // should be a.length - 1 - i
if (a[j] > a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
}
// CORRECT: inner loop shrinks
static void correct(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
}
public static void main(String[] args) {
System.out.println("Both produce correct output but buggy does more work.");
}
}
Both produce correct output but buggy does more work.
Visual Overview
Bubble Sort Pass-by-Pass:
Initial: [75000, 25000, 50000, 10000, 90000]
Pass 1: compare adjacent, swap if wrong order
[25000, 75000, 50000, 10000, 90000] swap 75K/25K
[25000, 50000, 75000, 10000, 90000] swap 75K/50K
[25000, 50000, 10000, 75000, 90000] swap 75K/10K
[25000, 50000, 10000, 75000, 90000] 90K already at end
Result: 90000 is in place ─────────────────── ▼
Pass 2: inner loop shrinks by 1
[25000, 10000, 50000, 75000, 90000]
Result: 75000 is in place ──────────── ▼
Pass 3:
[10000, 25000, 50000, 75000, 90000]
Result: 50000 is in place ─────── ▼
Pass 4: no swaps needed → DONE
Key Takeaway
Bubble sort is the simplest comparison-based sorting algorithm. It steps through the array comparing each pair of adjacent elements and swaps them when they are in the wrong order. After each pass the largest remaining element has bubbled to its final position at the end, so the inner loop shrinks by one.
The one essential optimisation is the swapped flag. If a pass completes without any swaps, the array is already sorted and the algorithm exits early, making bubble sort O(n) on sorted input. Without the flag, it always performs the full quadratic work.
Bubble sort is stable because it only swaps adjacent elements when one is strictly greater. It uses O(1) extra space. However, its O(n^2) average and worst-case time makes it unsuitable for any production use at the National Bank of India. It is valuable only as a teaching tool that clearly illustrates the comparison-and-swap mechanic.
The honest senior-level assessment is that bubble sort should never be shipped. For real sorting, use Java's Arrays.sort or Collections.sort, which are orders of magnitude faster.
Remember one sentence: bubble sort swaps adjacent out-of-order pairs until the largest bubbles to the end each pass, but its quadratic time makes it a teaching tool, not a production algorithm.
---