Bubble Sort Algorithm — O(n²) Sorting Guide

What is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly compares adjacent elements and swaps them if they are in the wrong order.

It is called "bubble" sort because after each pass, the largest unsorted element gradually moves toward the end of the array, as if it is bubbling upward.

Core Idea

Bubble Sort works by making repeated passes over the array:

1. Compare each pair of adjacent elements.
2. Swap them if the left element is greater than the right element.
3. Continue until the end of the current unsorted portion.
4. Repeat until the array becomes sorted.

After the first pass, the largest element is guaranteed to be in the last position. After the second pass, the second-largest element is fixed, and so on.

Why the Largest Element Settles After Each Pass

During one complete pass, whenever a larger element is on the left of a smaller element, they are swapped. Because of repeated adjacent swaps, the largest remaining element keeps moving right until it reaches the last unsorted position.

This is the key invariant of Bubble Sort: after each pass, the suffix at the end becomes sorted and does not need to be checked again.

Basic Bubble Sort vs Optimized Bubble Sort

The basic version always performs all passes, even if the array becomes sorted earlier. The optimized version uses a swapped flag and stops early if no swap happens during a pass.

This optimization is important because it changes the best-case running time from O(n^2) to O(n) for already sorted input.

Step-by-Step Example

Consider the array [5, 3, 8, 1, 2].

The array becomes sorted by repeatedly correcting local inversions between neighboring elements.

Algorithm Steps

1. Start from the first element.
2. Compare each adjacent pair.
3. If the pair is out of order, swap it.
4. Continue until the end of the unsorted part.
5. Reduce the unsorted range because the largest element is now fixed.
6. Stop early if a full pass makes no swaps.

Bubble Sort Implementations

public class BubbleSortBasic {

    static void bubbleSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

public class BubbleSortOptimized {

    static void bubbleSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }
        }
    }
}

Time and Space Complexity

Bubble Sort is an in-place algorithm because it uses only a constant amount of extra memory.

Why Bubble Sort Is Stable

A sorting algorithm is stable if equal elements keep their original relative order after sorting.

Bubble Sort is stable because it swaps elements only when the left element is strictly greater than the right one. Equal elements are not forced to cross each other.

Trace Example

For the array [64, 34, 25, 12, 22, 11, 90]:

Bubble Sort vs Selection Sort vs Insertion Sort

Advantages of Bubble Sort

• Very easy to understand and implement.
• Works in-place with O(1) extra space.
• Stable sorting algorithm.
• Optimized version can stop early for already sorted or nearly sorted data.

Limitations of Bubble Sort

• Very slow for large input sizes.
• Requires many comparisons and swaps.
• Usually much worse than Merge Sort, Quick Sort, or Heap Sort.
• Mainly useful for learning, not for serious performance-critical applications.

When to Use Bubble Sort

• For educational purposes when learning sorting basics.
• For very small arrays where performance is not important.
• For nearly sorted data when the optimized version is acceptable.

Avoid Bubble Sort for large or performance-sensitive datasets.

Common Mistakes

• Running the inner loop to the full end every time without shrinking the unsorted range.
• Forgetting the early-exit optimization when discussing best-case behavior.
• Confusing Bubble Sort with Selection Sort.
• Using Bubble Sort for large arrays where faster algorithms are clearly better.

Key Takeaways

• Bubble Sort repeatedly swaps adjacent elements that are in the wrong order.
• After each pass, the largest unsorted element reaches its correct position.
• The optimized version has O(n) best-case time for an already sorted array.
• Average and worst-case time complexity remain O(n^2).
• Bubble Sort is stable, in-place, and easy to learn, but inefficient for large data.