Idea: Repeatedly swap adjacent elements if they are in wrong order

• Time: O(n²)
• Space: O(1)
• Stable: ✅
• Used in practice? ❌

Interview note:

Mentioned only to test fundamentals.

import java.util.Arrays;

public class BubbleSort {
    public static void sort(int[] a) {
        boolean swapped;
        for (int i = 0; i < a.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    swapped = true;
                }
            }
            if (!swapped) return; // already sorted
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Watch for

• Adjacent swaps
• Largest element “bubbling” to the end
• Many repeated passes

Mental model: 🫧 Big numbers float right