Bubble Sort

Easy TUF ID 943 A2Z

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using the bubble sort algorithm: repeatedly compare adjacent elements and swap them when they are out of order, until the whole array is sorted.

Constraints: 1 ≤ n ≤ 10^3, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [13, 46, 24, 52, 20, 9]
answer = [9, 13, 20, 24, 46, 52]      // every element is <= the one after it

Example 2

arr = [1, 2, 3, 4, 5]
answer = [1, 2, 3, 4, 5]              // already sorted; a good implementation notices after one pass

Approach 1: Textbook bubble sort

Intuition. Walk the array from left to right comparing each element with its right neighbour and swapping when the left one is bigger. Watch what happens to the largest element during that walk: as soon as the sweep reaches it, every following comparison swaps it one step further right, so after one full pass the maximum sits at the last index. That element is done. Repeat the pass on the first n - 1 elements to fix the second largest, then on n - 2, and so on. After n - 1 passes only one element is left unfixed, and a single element is trivially in place.

The invariant is the mirror image of selection sort’s: after i passes, the suffix arr[n-i..n-1] holds the i largest elements in their final positions.

Algorithm.

For i from 0 to n - 2 (pass number):
For j from 0 to n - 2 - i:
If arr[j] > arr[j + 1], swap them.

The inner bound shrinks by one each pass because the last i elements are already final.

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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Dry run on arr = [13, 46, 24, 52, 20, 9], showing the array after each pass and the comparisons made:

pass i	comparisons	swaps in this pass	array after the pass
0	5	(46,24) (52,20) (52,9)	[13, 24, 46, 20, 9, 52]
1	4	(46,20) (46,9)	[13, 24, 20, 9, 46, 52]
2	3	(24,20) (24,9)	[13, 20, 9, 24, 46, 52]
3	2	(20,9)	[13, 9, 20, 24, 46, 52]
4	1	(13,9)	[9, 13, 20, 24, 46, 52]

Each pass pushes one more maximum into the growing sorted suffix on the right.

Complexity. Time O(n^2): pass i makes n - 1 - i comparisons, n(n-1)/2 in total, and this version always does all of them even if the array was sorted from the start. Space O(1): a temporary for the swap and two counters.

Approach 2: Early exit when a pass makes no swap

Intuition. A pass that performs zero swaps has verified that every adjacent pair is in order, and an array whose adjacent pairs are all in order is sorted. So the moment a pass finishes without swapping we can stop. On an already sorted input that happens in the very first pass, which turns the best case into O(n).

This is the version to write in an interview. It is the same code with a boolean flag, and the flag is what makes bubble sort adaptive: the closer the input is to sorted, the fewer passes it needs.

Algorithm.

For each pass, set swapped = false.
Run the usual inner loop; whenever a swap happens, set swapped = true.
After the inner loop, if swapped is still false, return.

static void bubbleSortEarlyExit(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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) return;
    }
}

Dry run on arr = [2, 1, 3, 4, 5, 6]:

pass i	swaps	array after the pass	swapped	action
0	(2,1)	[1, 2, 3, 4, 5, 6]	true	continue
1	none	[1, 2, 3, 4, 5, 6]	false	return

Two passes instead of five. On Example 2 ([1, 2, 3, 4, 5]) it is one pass of four comparisons and no swaps.

Complexity. Time O(n) best case (one pass), O(n^2) worst case (reversed input needs all n - 1 passes). Space O(1).

Note that the worst case is not improved: on [5, 4, 3, 2, 1] every pass swaps, so the flag never saves anything. Early exit helps only for inputs that become sorted before the n - 1 passes are used up.

Approach 3: Shrink the range to the last swap

Intuition. The early-exit flag is a one-bit summary of a pass. We can record more: the index of the last swap. If the last swap in a pass happened at positions (j, j + 1), then every pair from j + 1 onwards was compared without swapping, and the bubbling guarantees that arr[j + 1] is at least as large as everything before it. So arr[j + 1..end] is sorted and final, not just arr[end]. The next pass only needs to go up to j.

This subsumes approach 2: when a pass makes no swap, lastSwap stays 0, the range shrinks to nothing and the loop ends.

Algorithm.

Let end = n - 1 be the last index that still needs attention.
While end > 0: set lastSwap = 0, run the pass for j from 0 to end - 1, recording lastSwap = j on every swap.
Set end = lastSwap and repeat.

static void bubbleSortLastSwap(int[] arr) {
    int end = arr.length - 1;
    while (end > 0) {
        int lastSwap = 0;
        for (int j = 0; j < end; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                lastSwap = j;
            }
        }
        end = lastSwap;
    }
}

Complexity. Time O(n) best, O(n^2) worst, never more comparisons than approach 2 and often fewer. Space O(1).

On [2, 1, 3, 4, 5, 6] the first pass swaps only at j = 0, so end becomes 0 and the method finishes after one pass, where approach 2 needed a second pass to confirm. For a reversed array nothing changes: the last swap is always at end - 1.

Edge cases and pitfalls

Empty or single-element array. n - 1 is -1 or 0; the outer loop does not run and end > 0 is false. All three methods return immediately.
Inner bound off by one. The inner loop accesses arr[j + 1], so j must stop at n - 2 - i, i.e. the condition is j < n - 1 - i. Writing j < n - i throws ArrayIndexOutOfBoundsException on the first pass.
Strict > keeps the sort stable. Swapping only when arr[j] > arr[j + 1] never exchanges equal elements, so equal keys keep their relative order. Using >= would still sort but would destroy stability and add pointless swaps.
Compare with >, not subtraction. arr[j] - arr[j + 1] > 0 overflows for values near the int limits; the tests include Integer.MIN_VALUE and Integer.MAX_VALUE together.
Forgetting to reset the flag. swapped must be declared (or reset) inside the outer loop. Declared once outside, it stays true after the first swap and the early exit never fires.
Shrinking the range is not optional for correctness, but the bound is. Running the inner loop to n - 1 on every pass still sorts correctly; it just wastes comparisons on the already fixed suffix.
Worst case is real. Bubble sort on 10^5 reversed elements is about 5 × 10^9 comparisons; it is a teaching algorithm, not a production one.

Recursive Bubble Sort replaces the outer loop with a recursive call; the pass logic is identical.
Selection Sort also fixes one element per round but does it with a single swap instead of a chain of adjacent swaps.
Insertion Sorting is the other adaptive quadratic sort and is usually the better choice for nearly sorted data.
Merge Sorting is the first O(n log n) sort in the sheet.

Bubble Sort

Problem

Approach 1: Textbook bubble sort

Approach 2: Early exit when a pass makes no swap

Approach 3: Shrink the range to the last swap

Edge cases and pitfalls

Related problems