Bubble Sort in Java

Bubble sort is the simplest sorting algorithm: it repeatedly walks through the array, compares each pair of adjacent elements and swaps them if they are in the wrong order, until the whole array is sorted. It is a classic teaching algorithm — rarely used in production, but perfect for learning how sorting works, and a frequent interview question.

How bubble sort works

The idea of bubble sort: one step of the algorithm is a single pass over the array. Along the way we look at pairs of adjacent elements. If a pair is in the wrong order, we swap the two elements.

Let’s picture the array top–down, from the element at index 0 to the last one.

After the first pass, the smallest element “bubbles” up to the top — that is where the name bubble sort comes from. We repeat the pass for every element except the first one, which is already in place, and find the next smallest element. We keep going until the whole array is sorted.

Bubble sort in Java

Here is a bubble sort implementation in Java. The outer for loop counts the passes, and the inner loop compares adjacent elements within one pass. Values are swapped through a temporary variable tmp. In the inner loop we start from the end of the array (array.length - 1) and, on each new pass, shrink the range we scan (condition j > i), because the top positions are already sorted.

public class BubbleSorter {
    public static void sort(int[] array) {
        // i - the pass number
        for (int i = 0; i < array.length - 1; i++) {
            // inner loop of a single pass
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
}

Testing the algorithm

Let’s call BubbleSorter.sort() from the BubbleSorterTest class below. We sort each row of the two-dimensional array data, including the empty and single-element edge cases:

import java.util.Arrays;

public class BubbleSorterTest {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            BubbleSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

The program output — the original array on the left, the sorted one on the right:

[] => []
[1] => [1]
[0, 3, 2, 1] => [0, 1, 2, 3]
[4, 3, 2, 1, 0] => [0, 1, 2, 3, 4]
[6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7] => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 123]

Optimizing bubble sort

The basic version has a weakness: even if the array is already sorted, the algorithm still runs every pass. That is easy to fix. Add a boolean flag swapped and reset it at the start of each pass. If a full pass makes no swaps at all, the array is already in order and we can stop early.

public class OptimizedBubbleSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean swapped = false;
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                    swapped = true;
                }
            }
            // no swaps in this pass - the array is sorted
            if (!swapped) {
                break;
            }
        }
    }
}

Thanks to the flag, an already sorted (or almost sorted) array finishes in a single pass. This improves the best case from O(n²) to O(n), while the average and worst cases stay the same.

Time complexity (Big O)

Bubble sort runs nested passes over the array, so on average and in the worst case the number of comparisons is proportional to n², where n is the number of elements.

Pros, cons and when to use it

Pros:

• very simple implementation — easy to understand and write from memory;
• sorts in place, needs no extra memory (O(1));
• stable: equal elements are not reordered relative to each other;
• with the swapped-flag optimization it instantly detects an already sorted array.

Cons:

• quadratic O(n²) time — unacceptably slow on large arrays;
• performs many redundant swaps compared with, say, selection sort.

When bubble sort is a bad choice

For real-world data, use the built-in Arrays.sort() (a dual-pivot quicksort for primitives and stable TimSort for objects) — it runs in O(n·log n). Bubble sort makes sense only when the array is tiny or nearly sorted, and as a learning exercise or interview task. For large datasets choose quicksort, merge sort or heap sort instead.