Bubble Sort

A quadratic-time algorithm that’s only useful as a teaching tool — but still has a few subtle properties.

Context

Bubble sort shows up everywhere because it’s:

• easy to explain,
• easy to implement,
• easy to reason about correctness.

It’s almost never the right choice in production code.

Core idea

Bubble sort repeatedly compares adjacent elements and swaps them if they’re out of order.

After each pass:

• the largest unsorted element “bubbles” to the end,
• the effective search space shrinks by one.

Properties

• Time complexity
  • Worst-case and average time complexity: O(n²).
  • Best case (already sorted + early exit): O(n)
• Space complexity: O(1) (in-place)
• Stable: equal elements keep their relative order
• In-place: no extra memory beyond a few variables
• Adaptive: stops early if the array is already sorted

Implementation

class BubbleSort {
    void sort(int[] array) {
        for (var i = 0; i < array.length; i++) {
            var isUnchanged = true;
            
            for (var j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    var temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isUnchanged = false;
                }
            }
            
            if (isUnchanged) break;
        }
    }
}