Bubble Sort in Java

Picture students lining up by height for a class photo. The teacher walks along the line, and whenever two neighbors are in the wrong order, they swap places. After one walk, the tallest student has drifted all the way to the end. After a few more walks, everyone is in order. Bubble sort works exactly like that: big values "bubble up" to the end of the array, one pass at a time. It is rarely used in real programs, but it is the easiest sorting algorithm to understand, and interviewers still ask about it. In this lesson, you will learn how bubble sort works, trace it pass by pass, write an improved version that stops early, and see its cost.

What Is Bubble Sort?

Bubble sort in Java is a sorting algorithm that is used to arrange elements in order by repeatedly comparing neighboring elements and swapping them if they are in the wrong order. After each full pass, the largest remaining element is in its final place at the end.

• It sorts in place: no extra array is needed.
• It is stable: equal elements keep their original order.
• It is O(n²) in the average and worst case, so it is only practical for tiny arrays.

How It Works

1. Compare elements 0 and 1. If the first is bigger, swap them.
2. Compare elements 1 and 2, then 2 and 3, and so on to the end. The biggest value is now last.
3. Repeat the pass, but stop one position earlier each time, because the end is already sorted.
4. If a whole pass makes no swaps, the array is sorted and you can stop.

Bubble Sort with a Trace

Let's see an example that sorts five marks and prints the array after each pass.

import java.util.Arrays;
 
public class BubbleSort {
    static void bubbleSort(int[] a) {
        for (int pass = 1; pass < a.length; pass++) {
            boolean swapped = false;
            for (int i = 0; i < a.length - pass; i++) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
            System.out.println("after pass " + pass + ": "
                    + Arrays.toString(a));
            if (!swapped) {
                break;                     // no swaps: already sorted
            }
        }
    }
 
    public static void main(String[] args) {
        int[] marks = {29, 10, 14, 37, 13};
        bubbleSort(marks);
        System.out.println("sorted: " + Arrays.toString(marks));
    }
}

after pass 1: [10, 14, 29, 13, 37]
after pass 2: [10, 14, 13, 29, 37]
after pass 3: [10, 13, 14, 29, 37]
after pass 4: [10, 13, 14, 29, 37]
sorted: [10, 13, 14, 29, 37]

Explanation:

1. Pass 1 moves 37, the largest value, to the end. Along the way 29 also moves right past 10 and 14.
2. Pass 2 moves 29 into the second-last place. Each pass checks one fewer pair (a.length - pass), because the end is already sorted.
3. Pass 3 finishes the job, and pass 4 makes no swaps, so the swapped flag stops the loop.
4. The swap uses a temporary variable: temp holds one value while the other moves.

Why the Early Exit Matters

Without the swapped flag, bubble sort always makes n - 1 passes, even on an array that is already sorted. With the flag, a sorted array needs just one pass of n - 1 comparisons.

public class SortedInput {
    public static void main(String[] args) {
        int[] a = {10, 13, 14, 29, 37};
        int comparisons = 0;
        for (int pass = 1; pass < a.length; pass++) {
            boolean swapped = false;
            for (int i = 0; i < a.length - pass; i++) {
                comparisons++;
                if (a[i] > a[i + 1]) {
                    int t = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = t;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
        System.out.println("comparisons on sorted input: " + comparisons);
    }
}

comparisons on sorted input: 4

Explanation: the first pass finds no pair out of order, so the loop stops after 4 comparisons. Without the flag, it would make 4 + 3 + 2 + 1 = 10.

Complexity

For 10,000 elements, the worst case is about 50 million comparisons. Arrays.sort sorts the same array in a tiny fraction of the time.

Common Mistakes

Inner loop running to a.length - 1 every pass. It still works, but it wastes comparisons on the sorted end. Use a.length - pass.

Inner loop running to a.length. Then a[i + 1] reads past the end and throws ArrayIndexOutOfBoundsException.

Swapping without a temporary variable. a[i] = a[i + 1]; a[i + 1] = a[i]; copies the same value into both places.

Using >= instead of >. It swaps equal elements and makes the sort unstable.

Practice

1. Easy: Change the comparison so the array is sorted in descending order. Trace it on {29, 10, 14, 37, 13}.
2. Harder: Add a counter for swaps as well as comparisons. Run the sort on {37, 29, 14, 13, 10} (reverse order) and check that the comparisons equal n(n - 1) / 2.

Key Takeaways