Bubble Sort Algorithm O n² Sorting: Tutorial, Examples, FAQs & Interview Tips

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:

Compare each pair of adjacent elements.
Swap them if the left element is greater than the right element.
Continue until the end of the current unsorted portion.
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].

Pass	What Happens	Array After Pass
Pass 1	5 swaps with 3, then 8 swaps past 1 and 2	[3, 5, 1, 2, 8]
Pass 2	5 swaps with 1 and 2	[3, 1, 2, 5, 8]
Pass 3	3 swaps with 1 and 2	[1, 2, 3, 5, 8]
Pass 4	No swap needed	[1, 2, 3, 5, 8]

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

Algorithm Steps

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

Bubble Sort Implementations

Basic and Optimized Bubble Sort

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

Case	Time Complexity	Space Complexity	Explanation
Best case	O(n)	O(1)	Already sorted array with optimization
Average case	O(n^2)	O(1)	Typical unsorted input
Worst case	O(n^2)	O(1)	Reverse-sorted array

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]:

Pass	Array State	Observation
Initial	[64, 34, 25, 12, 22, 11, 90]	Unsorted array
Pass 1	[34, 25, 12, 22, 11, 64, 90]	90 is already largest, 64 moves near the end
Pass 2	[25, 12, 22, 11, 34, 64, 90]	64 reaches its final position
Pass 3	[12, 22, 11, 25, 34, 64, 90]	34 becomes fixed
Pass 4	[12, 11, 22, 25, 34, 64, 90]	25 becomes fixed
Pass 5	[11, 12, 22, 25, 34, 64, 90]	Array becomes sorted

Bubble Sort vs Selection Sort vs Insertion Sort

Aspect	Bubble Sort	Selection Sort	Insertion Sort
Main idea	Swap adjacent out-of-order elements	Select minimum and place it correctly	Insert each element into the sorted portion
Best case	O(n) with optimization	O(n^2)	O(n)
Stable	Yes	No	Yes
Swaps / shifts	Can be many swaps	Usually fewer swaps	Usually many shifts
Best use case	Teaching and small nearly sorted input	When writes are expensive	Small or nearly sorted arrays

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.

Previous Next