Imagine students standing in a line for a class photo, and the teacher wants them arranged from shortest to tallest.
The teacher walks along the line and looks at two neighbouring students at a time. If the one on the left is taller than the one on the right, they swap places. Then the teacher moves one step to the right and repeats.
After one full walk, the tallest student has moved all the way to the end of the line. The teacher then walks again, and the second tallest reaches its place. This continues until nobody needs to swap.
That is exactly how Bubble Sort works.
In the previous chapter, we got an overview of sorting algorithms. Bubble Sort is the simplest of them, and it is usually the first sorting algorithm everyone learns.
What is Bubble Sort?
Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the array, compares each pair of adjacent elements, and swaps them if they are in the wrong order.
It is called Bubble Sort because, just like air bubbles rising to the top of water, the largest elements gradually "bubble up" to the end of the array with each pass.
The core rule is tiny:
if arr[j] > arr[j + 1]
swap themEverything else is just repeating this rule enough times.
How Bubble Sort Works
Let's sort this array in ascending order:
[5, 1, 4, 2, 8]Pass 1
[5, 1, 4, 2, 8] compare 5 and 1 → 5 > 1 → swap
↑ ↑
[1, 5, 4, 2, 8] compare 5 and 4 → 5 > 4 → swap
↑ ↑
[1, 4, 5, 2, 8] compare 5 and 2 → 5 > 2 → swap
↑ ↑
[1, 4, 2, 5, 8] compare 5 and 8 → 5 < 8 → no swap
↑ ↑
[1, 4, 2, 5, 8] ← end of pass 1The largest element, 8, is now at the end. (Here it was already there, but if it had been anywhere else, this pass would have carried it to the end.) It is in its final position, so we never need to look at it again.
Pass 2
We now only need to go up to index 3, because the last element is already fixed.
[1, 4, 2, 5 | 8] compare 1 and 4 → no swap
[1, 4, 2, 5 | 8] compare 4 and 2 → swap
[1, 2, 4, 5 | 8] compare 4 and 5 → no swap
[1, 2, 4, 5 | 8] ← end of pass 2Now 5 and 8 are both in their final positions.
Pass 3
[1, 2, 4 | 5, 8] compare 1 and 2 → no swap
[1, 2, 4 | 5, 8] compare 2 and 4 → no swap
No swaps in this pass → the array is sorted!If a complete pass makes zero swaps, every neighbouring pair is already in order, which means the whole array is sorted. We can stop early.
After pass k, the k largest elements are in their final positions at the end of the array.
That is why each pass can be one comparison shorter than the previous one.
The Algorithm
1. Repeat for pass i = 0, 1, 2, ..., n - 2:
2. swapped = false
3. For j = 0 to n - 2 - i:
4. If arr[j] > arr[j + 1]:
5. swap arr[j] and arr[j + 1]
6. swapped = true
7. If swapped is false, stop (array is sorted)Two loops:
The outer loop counts the passes. At most
n - 1passes are needed, because oncen - 1elements are in their final places, the last one must be too.The inner loop compares neighbours. It stops at
n - 1 - ibecause the lastielements are already sorted, and because we accessarr[j + 1].
Bubble Sort in Java
Here is the full program. It also prints the array after every pass, so you can see the algorithm working:
import java.util.Arrays;
class Main {
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
// The last i elements are already in place
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("After pass " + (i + 1) + ": " + Arrays.toString(arr));
// No swaps means the array is already sorted
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
System.out.println("Original: " + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("Sorted: " + Arrays.toString(arr));
}
}Output:
Original: [5, 1, 4, 2, 8]
After pass 1: [1, 4, 2, 5, 8]
After pass 2: [1, 2, 4, 5, 8]
After pass 3: [1, 2, 4, 5, 8]
Sorted: [1, 2, 4, 5, 8]The output matches our hand trace exactly. Pass 3 made no swaps, so the loop stopped after 3 passes instead of the maximum 4.
Swapping uses a temporary variable, the same three-step swap you have seen before:
temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = tempThe swapped Flag: Basic vs Optimized
The swapped flag is a small change that makes a big difference on sorted or nearly sorted input.
Without the flag, Bubble Sort always does all n - 1 passes, even if the array was sorted from the start. With the flag, it stops after the first pass that makes no swaps.
Let's measure both versions by counting comparisons and swaps:
import java.util.Arrays;
class Main {
static int comparisons;
static int swaps;
// Basic version: no early exit
static void bubbleSortBasic(int[] arr) {
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swaps++;
}
}
}
}
// Optimized version: stops when a pass makes no swaps
static void bubbleSortOptimized(int[] arr) {
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swaps++;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
// Descending order for Strings
static void bubbleSortDescending(String[] 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) { // flip the comparison
String temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
static void report(String label, int[] input, boolean optimized) {
int[] copy = input.clone();
if (optimized) {
bubbleSortOptimized(copy);
} else {
bubbleSortBasic(copy);
}
System.out.println(label + " " + Arrays.toString(input)
+ " -> comparisons = " + comparisons + ", swaps = " + swaps);
}
public static void main(String[] args) {
int[] sorted = {1, 2, 3, 4, 5, 6};
int[] reversed = {6, 5, 4, 3, 2, 1};
int[] random = {3, 6, 1, 5, 2, 4};
report("Basic, sorted ", sorted, false);
report("Optimized, sorted ", sorted, true);
report("Optimized, reversed", reversed, true);
report("Optimized, random ", random, true);
String[] names = {"Diya", "Aarav", "Rohan", "Kabir"};
bubbleSortDescending(names);
System.out.println("Names Z to A: " + Arrays.toString(names));
}
}Output:
Basic, sorted [1, 2, 3, 4, 5, 6] -> comparisons = 15, swaps = 0
Optimized, sorted [1, 2, 3, 4, 5, 6] -> comparisons = 5, swaps = 0
Optimized, reversed [6, 5, 4, 3, 2, 1] -> comparisons = 15, swaps = 15
Optimized, random [3, 6, 1, 5, 2, 4] -> comparisons = 14, swaps = 8
Names Z to A: [Rohan, Kabir, Diya, Aarav]What this tells us:
On already sorted data, the basic version wastes 15 comparisons. The optimized version notices after one pass (5 comparisons) that nothing moved and stops.
On reversed data, both versions do the maximum work: every comparison causes a swap.
To sort in descending order, or to sort Strings, only the comparison changes. For Strings we use
compareTo(), which returns a negative number when the first string comes before the second alphabetically.
Time Complexity
Let's count the comparisons when all passes run. With n elements:
Pass 1 → n - 1 comparisons
Pass 2 → n - 2 comparisons
Pass 3 → n - 3 comparisons
...
Last → 1 comparison
Total = (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2For n = 6: 6 × 5 / 2 = 15, which matches the program output above.
n(n - 1)/2 grows like n²/2, so after dropping constants, it is O(n²).
Best Case — O(n)
The array is already sorted. With the swapped flag, the first pass makes n - 1 comparisons, finds no swaps and stops.
Without the flag, even the best case is O(n²).
Worst Case — O(n²)
The array is sorted in reverse order. Every comparison leads to a swap, and all passes are needed.
Average Case — O(n²)
For random data, the number of comparisons and swaps still grows in proportion to n² (on average about n(n - 1)/4 swaps, as we will see in the inversions section below).
Space Complexity — O(1)
Only a few variables (i, j, temp, swapped) are used, no matter how large the array is. Bubble Sort is an in-place algorithm.
Case | Time | When |
|---|---|---|
Best | O(n) | Already sorted (with swapped flag) |
Average | O(n²) | Random order |
Worst | O(n²) | Reverse sorted |
Space | O(1) | Always |
Swaps and Inversions
Here is a neat fact that interviewers sometimes ask about.
An inversion is a pair of positions (i, j) where i < j but arr[i] > arr[j]. In other words, a pair of elements that are in the wrong order relative to each other.
For [3, 6, 1, 5, 2, 4], the inversions are:
(3,1) (3,2)
(6,1) (6,5) (6,2) (6,4)
(5,2) (5,4)
Total = 8Each Bubble Sort swap exchanges two neighbours that are out of order, which fixes exactly one inversion. So:
The number of swaps Bubble Sort makes is always equal to the number of inversions in the array.
Our program printed swaps = 8 for this array, exactly as expected. A reversed array of 6 elements has the maximum possible 6 × 5 / 2 = 15 inversions, which also matches.
For a randomly ordered array, each of the n(n - 1)/2 pairs is inverted with probability one half, so on average there are about n(n - 1)/4 inversions, and therefore about that many swaps. That is still O(n²).
Properties of Bubble Sort
Stable — Yes
We only swap when arr[j] > arr[j + 1]. Two equal elements are never swapped, so their original order is preserved. (If you change the condition to >=, the algorithm still sorts, but it becomes unstable and does useless swaps.)
In-Place — Yes
It uses O(1) extra memory.
Adaptive — Yes (with the flag)
It finishes in O(n) on sorted input and stops early on nearly sorted input.
Comparison-Based — Yes
It decides the order only by comparing pairs of elements.
Common Mistakes
1. Going Out of Bounds
// WRONG
for (int j = 0; j < n; j++) {
if (arr[j] > arr[j + 1]) { ... } // arr[n] does not exist
}When j = n - 1, arr[j + 1] is arr[n], which throws an ArrayIndexOutOfBoundsException. The inner loop must stop at j < n - 1 - i (or at least j < n - 1).
2. Forgetting to Shrink the Inner Loop
Using j < n - 1 every time still gives a correct result, but wastes comparisons on the already-sorted tail.
3. Resetting swapped in the Wrong Place
The swapped flag must be set to false at the start of every pass, inside the outer loop. If you declare it once outside the outer loop and never reset it, it stays true after the first swap and the early exit never happens.
4. Using >= Instead of >
This makes the sort unstable, as explained above.
When Should You Use Bubble Sort?
Honestly, almost never in real projects. For large data, O(n²) is far too slow, and even among simple sorts, Insertion Sort usually performs better.
Bubble Sort is still useful for:
Learning the ideas of comparing and swapping
Very small arrays where simplicity matters more than speed
Quickly checking whether an array is sorted (one pass with no swaps)
Interviews, where you may be asked to write it, trace it, or explain its complexity and stability
Interview Tips and Practice
Be ready to trace a pass by hand, like we did with
[5, 1, 4, 2, 8].Always mention the
swappedoptimization and that it makes the best caseO(n).Remember: after pass
k, theklargest elements are at the end.Know that swaps = number of inversions.
Practice:
Sort an array in descending order using Bubble Sort.
Sort an array of Strings by length using Bubble Sort.
Count the number of swaps Bubble Sort would make, without actually sorting (hint: count inversions).
Write a version where each pass moves the smallest element to the front by going from right to left.
How many passes does the optimized version need for
[2, 3, 4, 5, 1]? And for[5, 1, 2, 3, 4]? (Try it, the answers are very different.)
The Main Idea
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, so the largest unsorted element "bubbles" to the end on every pass.
For each pass:
Compare arr[j] and arr[j + 1]
↓
Wrong order? → Swap
↓
Largest element reaches the end
↓
No swaps in a pass? → Stop, array is sortedThe facts to remember:
Best case → O(n) (already sorted, with swapped flag)
Worst case → O(n²) (reverse sorted)
Space → O(1)
Stable → Yes
In-place → YesBubble Sort is simple to understand and code, but its O(n²) time makes it a learning tool rather than a practical choice. Next, we look at Selection Sort, which uses far fewer swaps.