Bubble Sort
What Is Bubble Sort?
Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element has "bubbled up" to its correct position at the end.
One pass through [5, 3, 8, 1, 2]:
Compare 5,3: 5 > 3 → SWAP → [3, 5, 8, 1, 2]
Compare 5,8: 5 < 8 → no → [3, 5, 8, 1, 2]
Compare 8,1: 8 > 1 → SWAP → [3, 5, 1, 8, 2]
Compare 8,2: 8 > 2 → SWAP → [3, 5, 1, 2, 8]
↑ 8 is now in final position
After pass 1: the largest element (8) is at its final index.
After pass 2: the second-largest is at its final index.
...and so on.
The name comes from how larger elements "bubble up" toward the end with each pass.
Basic Bubble Sort
1public class BubbleSort {
2
3 public static void bubbleSort(int[] arr) {
4 int n = arr.length;
5
6 for (int i = 0; i < n - 1; i++) {
7 // Each pass places the largest unsorted element at arr[n-1-i]
8 for (int j = 0; j < n - 1 - i; j++) {
9 if (arr[j] > arr[j + 1]) {
10 // Swap adjacent elements
11 int temp = arr[j];
12 arr[j] = arr[j + 1];
13 arr[j + 1] = temp;
14 }
15 }
16 }
17 }
18
19 public static void main(String[] args) {
20 int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
21 bubbleSort(arr1);
22 System.out.println(java.util.Arrays.toString(arr1));
23 // [11, 12, 22, 25, 34, 64, 90]
24
25 int[] arr2 = {5, 1, 4, 2, 8};
26 bubbleSort(arr2);
27 System.out.println(java.util.Arrays.toString(arr2));
28 // [1, 2, 4, 5, 8]
29
30 int[] single = {42};
31 bubbleSort(single);
32 System.out.println(java.util.Arrays.toString(single)); // [42]
33
34 int[] empty = {};
35 bubbleSort(empty);
36 System.out.println(java.util.Arrays.toString(empty)); // []
37 }
38}Output:
[11, 12, 22, 25, 34, 64, 90]
[1, 2, 4, 5, 8]
Complete Dry Run: [5, 1, 4, 2, 8]
Tracing every comparison and swap across all passes:
arr = [5, 1, 4, 2, 8] n=5 PASS 1 (i=0): inner loop j=0..3 j=0: arr[0]=5 > arr[1]=1 → SWAP [1, 5, 4, 2, 8] j=1: arr[1]=5 > arr[2]=4 → SWAP [1, 4, 5, 2, 8] j=2: arr[2]=5 > arr[3]=2 → SWAP [1, 4, 2, 5, 8] j=3: arr[3]=5 > arr[4]=8 → no [1, 4, 2, 5, 8] After pass 1: [1, 4, 2, 5, 8] ← 8 is in final position ✓ PASS 2 (i=1): inner loop j=0..2 j=0: arr[0]=1 > arr[1]=4 → no [1, 4, 2, 5, 8] j=1: arr[1]=4 > arr[2]=2 → SWAP [1, 2, 4, 5, 8] j=2: arr[2]=4 > arr[3]=5 → no [1, 2, 4, 5, 8] After pass 2: [1, 2, 4, 5, 8] ← 5 is in final position ✓ PASS 3 (i=2): inner loop j=0..1 j=0: arr[0]=1 > arr[1]=2 → no [1, 2, 4, 5, 8] j=1: arr[1]=2 > arr[2]=4 → no [1, 2, 4, 5, 8] After pass 3: [1, 2, 4, 5, 8] ← 4 is in final position ✓ PASS 4 (i=3): inner loop j=0..0 j=0: arr[0]=1 > arr[1]=2 → no [1, 2, 4, 5, 8] After pass 4: [1, 2, 4, 5, 8] ← 2 is in final position ✓ Total comparisons: 4 + 3 + 2 + 1 = 10 = n(n-1)/2 = 5×4/2 ✓ Total swaps: 4
Optimised Bubble Sort: Early-Exit Flag
If no swap occurs during a full pass, the array is already sorted — there is no point continuing. A single boolean flag tracks this and converts the best case from O(n²) to O(n).
1public class OptimisedBubbleSort {
2
3 public static void bubbleSortOptimised(int[] arr) {
4 int n = arr.length;
5
6 for (int i = 0; i < n - 1; i++) {
7 boolean swapped = false; // Flag: did any swap occur this pass?
8
9 for (int j = 0; j < n - 1 - i; j++) {
10 if (arr[j] > arr[j + 1]) {
11 int temp = arr[j];
12 arr[j] = arr[j + 1];
13 arr[j + 1] = temp;
14 swapped = true; // A swap happened
15 }
16 }
17
18 // If no swap in this pass — array is sorted
19 if (!swapped) {
20 System.out.println(" Early exit at pass " + (i + 1));
21 break;
22 }
23 }
24 }
25
26 public static void main(String[] args) {
27 // Already sorted — should exit after 1 pass
28 int[] sorted = {1, 2, 3, 4, 5};
29 bubbleSortOptimised(sorted);
30 System.out.println(java.util.Arrays.toString(sorted));
31 // Early exit at pass 1
32 // [1, 2, 3, 4, 5]
33
34 // One element out of place
35 int[] nearSorted = {1, 2, 4, 3, 5};
36 bubbleSortOptimised(nearSorted);
37 System.out.println(java.util.Arrays.toString(nearSorted));
38 // Early exit at pass 2
39 // [1, 2, 3, 4, 5]
40
41 // Reverse sorted — worst case, no early exit
42 int[] reversed = {5, 4, 3, 2, 1};
43 bubbleSortOptimised(reversed);
44 System.out.println(java.util.Arrays.toString(reversed));
45 // [1, 2, 3, 4, 5]
46 }
47}Output:
Early exit at pass 1
[1, 2, 3, 4, 5]
Early exit at pass 2
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
Dry Run: Early Exit on [1, 2, 3, 4, 5]
arr = [1, 2, 3, 4, 5] already sorted PASS 1 (i=0): swapped=false j=0: 1 > 2? No j=1: 2 > 3? No j=2: 3 > 4? No j=3: 4 > 5? No swapped still false → BREAK immediately Total comparisons: 4 = n-1 (one pass only) Total swaps: 0 Without optimisation: 4+3+2+1=10 comparisons With early exit: 4 comparisons — 2.5× fewer
Further Optimisation: Last Sorted Boundary
After each pass, every element after the last swap position is already in its final sorted position. The next pass only needs to go up to that position — not the full unsorted length.
Example: [1, 3, 2, 4, 5, 6] (4,5,6 already sorted) PASS 1: inner loop j=0..4 j=0: 1>3? No j=1: 3>2? YES SWAP → last_swap=1 [1,2,3,4,5,6] j=2: 3>4? No j=3: 4>5? No j=4: 5>6? No last_swap=1 → next pass only needs j=0..0 (up to index 1) PASS 2: inner loop j=0..0 j=0: 1>2? No swapped=false → EARLY EXIT Total comparisons: 5 + 1 = 6 Standard (without this): 4+3+2+1 = 10 comparisons
1public class BubbleSortBoundary {
2
3 public static void bubbleSortBoundary(int[] arr) {
4 int n = arr.length;
5 int boundary = n - 1; // Last index to compare up to
6
7 while (boundary > 0) {
8 int lastSwap = 0; // Track index of last swap this pass
9
10 for (int j = 0; j < boundary; j++) {
11 if (arr[j] > arr[j + 1]) {
12 int temp = arr[j];
13 arr[j] = arr[j + 1];
14 arr[j + 1] = temp;
15 lastSwap = j; // Record position of this swap
16 }
17 }
18
19 boundary = lastSwap; // Everything after lastSwap is sorted
20 }
21 }
22
23 public static void main(String[] args) {
24 int[] arr = {1, 3, 2, 4, 5, 6};
25 bubbleSortBoundary(arr);
26 System.out.println(java.util.Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6]
27
28 int[] arr2 = {64, 34, 25, 12, 22, 11, 90};
29 bubbleSortBoundary(arr2);
30 System.out.println(java.util.Arrays.toString(arr2)); // [11, 12, 22, 25, 34, 64, 90]
31 }
32}Output:
[1, 2, 3, 4, 5, 6]
[11, 12, 22, 25, 34, 64, 90]
Why Bubble Sort Is Stable
Bubble sort only swaps two adjacent elements when arr[j] > arr[j+1] — strictly greater. When two elements are equal (arr[j] == arr[j+1]), no swap occurs. Equal elements are never moved past each other, so their original relative order is always preserved.
Input: [(A,3), (B,1), (C,3), (D,2)] sort by number
Pass 1:
Compare (A,3),(B,1): 3>1 → SWAP [(B,1),(A,3),(C,3),(D,2)]
Compare (A,3),(C,3): 3>3? NO [(B,1),(A,3),(C,3),(D,2)] ← A stays before C!
Compare (C,3),(D,2): 3>2 → SWAP [(B,1),(A,3),(D,2),(C,3)]
...after all passes:
[(B,1),(D,2),(A,3),(C,3)]
↑ ↑
A still before C — original relative order preserved ✓
STABLE SORT CONFIRMED: equal elements (A,3) and (C,3) keep their original order.
Counting Comparisons and Swaps
Basic bubble sort — n=5 array: Pass 1 (i=0): j runs 0..3 → 4 comparisons (n-1) Pass 2 (i=1): j runs 0..2 → 3 comparisons (n-2) Pass 3 (i=2): j runs 0..1 → 2 comparisons (n-3) Pass 4 (i=3): j runs 0..0 → 1 comparison (n-4) Total comparisons = 4+3+2+1 = n(n-1)/2 = 10 Worst case (reverse sorted [5,4,3,2,1]): Every comparison triggers a swap Total swaps = n(n-1)/2 = 10 Best case (already sorted [1,2,3,4,5]): Basic: 10 comparisons, 0 swaps (still visits all — wastes time) Optimised (early exit): 4 comparisons (one pass), 0 swaps → O(n) Average case: Expected swaps ≈ n(n-1)/4 (each pair out of order with probability 1/2) Still O(n²) comparisons
Complexity Summary
| Variant | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Basic | O(n²) | O(n²) | O(n²) | O(1) | ✓ Yes |
| Optimised (early exit) | O(n) | O(n²) | O(n²) | O(1) | ✓ Yes |
| Boundary optimisation | O(n) | O(n²) | O(n²) | O(1) | ✓ Yes |
The early-exit optimisation is free — add one boolean flag. Always use the optimised version. The boundary optimisation provides a smaller constant factor in practice but keeps the same asymptotic complexity.
Common Mistakes
Using arr[j] >= arr[j+1] instead of arr[j] > arr[j+1]. The >= condition swaps equal elements, making the sort unstable. Always use strict > for ascending stable sort.
Wrong inner loop bound — j < n - 1 instead of j < n - 1 - i. Without - i, the inner loop checks already-sorted positions at the end on every pass. The algorithm still produces the correct result but does redundant work — O(n²) comparisons even in the best case with early exit, because the loop always runs all the way to the end.
Forgetting to reset swapped = false at the start of each outer loop iteration. If swapped is declared outside both loops (or not reset), the flag from a previous pass carries over and may incorrectly trigger early exit.
Confusing the number of passes needed. The outer loop runs n - 1 times — not n times. After n - 1 passes, the entire array is sorted. The last pass places the second-smallest in its correct position, leaving the smallest at index 0 automatically.
Interview Questions
Q: What is the time complexity of bubble sort and why?
O(n²) average and worst case. The algorithm makes n-1 passes. Pass i makes n-1-i comparisons. Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²). The optimised variant achieves O(n) best case for already-sorted input — one pass confirms no swaps needed and the algorithm terminates.
Q: Why is bubble sort stable?
Because it only swaps adjacent elements when arr[j] > arr[j+1] — strictly greater than. Equal elements (arr[j] == arr[j+1]) are never swapped, so they never change their relative positions. This guarantees that equal elements appear in the same order in the output as in the input.
Q: When would you ever use bubble sort in practice?
Almost never for production code — O(n²) is too slow for large inputs. The two situations where it is legitimate: (1) the input is known to be nearly sorted and early-exit makes it effectively O(n), or (2) the array is tiny (n ≤ 10) and simplicity of implementation matters more than performance. It is primarily used as an educational tool to understand comparison-based sorting, adjacent swaps, and the concept of stability.
FAQs
Can bubble sort sort in descending order?
Yes — change the comparison from arr[j] > arr[j+1] to arr[j] < arr[j+1]. This causes the smallest element to bubble to the end at each pass, giving descending order. Alternatively, sort ascending and then reverse the array.
Does the early-exit optimisation change the worst-case complexity?
No. For a reverse-sorted array, every comparison triggers a swap — the swapped flag is true at the end of every pass and early exit never fires. The algorithm still runs all n-1 passes. Worst-case remains O(n²). The optimisation only helps when the input is already sorted or nearly sorted.
How does bubble sort compare to insertion sort?
Both are O(n²) average and worst case, O(n) best case with optimisation, O(1) space, and stable. Insertion sort is generally faster in practice because it does fewer comparisons and swaps — it moves an element to its correct position in one conceptual step rather than bubbling it one position at a time across many passes. Insertion sort is the preferred simple sort for small arrays or nearly-sorted data. Bubble sort is mainly used for teaching.
Summary
Bubble sort makes n-1 passes through the array. Each pass compares adjacent pairs and swaps them if out of order, causing the largest unsorted element to "bubble" to its final position at the end.
Three versions — each built on the previous:
Basic: Two nested loops. Outer: pass index i from 0 to n-2. Inner: j from 0 to n-2-i. Swap if arr[j] > arr[j+1]. Total comparisons: n(n-1)/2.
Optimised (early exit): Add swapped = false before inner loop; set swapped = true on any swap; break outer loop if swapped is still false after a full pass. Best case becomes O(n) — one pass confirms sorted.
Boundary tracking: Track lastSwap index during each pass; set boundary = lastSwap for the next pass. Skips comparisons of the already-sorted suffix — reduces constant factor without changing asymptotic complexity.
Key properties:
- ›Stable — equal elements never swapped (
>not>=) - ›In-place — O(1) space
- ›Adaptive — O(n) best case with early exit
- ›Simple — minimal implementation, good for teaching adjacent-swap mechanics
In the next topic, you will explore Selection Sort — an alternative O(n²) sort that makes exactly n-1 swaps (one per pass) instead of potentially n(n-1)/2 swaps like bubble sort.
What is the worst-case time complexity of bubble sort?