Bubble Sort
What is Bubble Sort?
Bubble sort is the simplest sorting algorithm. It repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end.
| Case | Time | Space | Stable? |
|---|---|---|---|
| Best | O(n) — already sorted (with optimization) | O(1) | Yes |
| Average | O(n²) | O(1) | Yes |
| Worst | O(n²) — reverse sorted | O(1) | Yes |
How it Works
For array [5, 3, 8, 1, 2]:
- Pass 1: Compare (5,3)→swap, (5,8)→ok, (8,1)→swap, (8,2)→swap →
[3, 5, 1, 2, 8] - Pass 2: Compare (3,5)→ok, (5,1)→swap, (5,2)→swap →
[3, 1, 2, 5, 8] - Pass 3: Compare (3,1)→swap, (3,2)→swap →
[1, 2, 3, 5, 8] - Pass 4: Compare (1,2)→ok →
[1, 2, 3, 5, 8]✓
import java.util.Arrays;
public class BubbleSort {
// Basic bubble sort — O(n²) always
static void bubbleSortBasic(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
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;
}
}
}
}
// Optimized bubble sort — O(n) best case (already sorted)
static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean 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; // no swaps → already sorted → stop early
}
}
public static void main(String[] args) {
int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before: " + Arrays.toString(arr1));
bubbleSortOptimized(arr1);
System.out.println("After: " + Arrays.toString(arr1));
// After: [11, 12, 22, 25, 34, 64, 90]
// Already sorted — exits after 1 pass (O(n))
int[] sorted = {1, 2, 3, 4, 5};
bubbleSortOptimized(sorted);
System.out.println("Already sorted: " + Arrays.toString(sorted));
}
}
/*
* When to use Bubble Sort:
* - Educational purposes (easy to understand)
* - Very small arrays (n < 20)
* - Nearly sorted data (with optimization)
*
* When NOT to use:
* - Large datasets — O(n²) is too slow
* - Use Merge Sort or Quick Sort instead
*/Step-by-Step Trace
For array [64, 34, 25, 12, 22, 11, 90] — showing each pass:
| Pass | Array State | Swaps |
|---|---|---|
| Initial | [64, 34, 25, 12, 22, 11, 90] | — |
| Pass 1 | [34, 25, 12, 22, 11, 64, 90] | 5 swaps — 90 bubbles to end |
| Pass 2 | [25, 12, 22, 11, 34, 64, 90] | 4 swaps — 64 bubbles to position |
| Pass 3 | [12, 22, 11, 25, 34, 64, 90] | 3 swaps |
| Pass 4 | [12, 11, 22, 25, 34, 64, 90] | 2 swaps |
| Pass 5 | [11, 12, 22, 25, 34, 64, 90] | 1 swap |
| Pass 6 | [11, 12, 22, 25, 34, 64, 90] | 0 swaps — done! |
When to Use Bubble Sort
- Educational purposes — easiest sorting algorithm to understand
- Very small arrays (n < 20) — overhead is negligible
- Nearly sorted data — with optimization, exits early in O(n)
- Avoid for large datasets — O(n²) is too slow