Bubble, Selection & Insertion Sort

These three sorting algorithms are usually the first ones anyone learns, and all three run in O(n²) time in the worst case — meaning they get painfully slow on large inputs. So why bother? Because they build the intuition every later, faster sort is built on: comparing elements, deciding when to swap, and reasoning about what "sorted so far" means. And one of them, insertion sort, is genuinely useful in production code — not despite being simple, but because of it.

Bubble Sort

Bubble sort repeatedly steps through the array, comparing each adjacent pair and swapping them if they're out of order. With every full pass, the largest unsorted element "bubbles up" to its correct position at the end. A pass with zero swaps means the array is already sorted, so the algorithm can stop early.

public 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 - 1 - i; 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;              // no swaps this pass — already sorted, stop early
        }
    }
}

Trace on [5, 1, 4, 2, 8]: Pass 1 compares (5,1)→swap, (5,4)→swap, (5,2)→swap, (5,8)→no swap, giving [1, 4, 2, 5, 8]. Pass 2 compares (1,4)→no, (4,2)→swap, (4,5)→no, giving [1, 2, 4, 5, 8]. Pass 3 makes zero swaps — the array is sorted and the loop exits early instead of running two more full passes.

Time complexity: O(n²) worst and average case — nested loops each roughly of size n. Best case O(n) when the array is already sorted, thanks to the early-exit flag. Space complexity: O(1) — sorting happens in place with one temp variable.

Selection Sort

Selection sort splits the array into a sorted prefix and an unsorted remainder. On each pass, it scans the entire unsorted remainder to find the minimum, then swaps that minimum into the next position of the sorted prefix. Unlike bubble sort, it cannot exit early — it always scans the full remaining range even if the array is already sorted.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Trace on [64, 25, 12, 22, 11]: scan the whole array, minimum is 11 at index 4 — swap with index 0, giving [11, 25, 12, 22, 64]. Scan indices 1-4, minimum is 12 at index 2 — swap with index 1, giving [11, 12, 25, 22, 64]. Scan indices 2-4, minimum is 22 at index 3 — swap with index 2, giving [11, 12, 22, 25, 64]. Remaining elements are already in place.

Time complexity: O(n²) in every case — best, average, and worst — because the inner scan for the minimum always runs over the full remaining range regardless of the input's initial order. Space complexity: O(1).

Insertion Sort

Insertion sort also grows a sorted prefix, but works the opposite way from selection sort: it takes the next unsorted element (the "key") and shifts it leftward past every already-sorted element that's bigger than it, inserting it into the correct spot. This is exactly how most people sort playing cards in their hand.

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];   // shift the bigger element right
            j--;
        }
        arr[j + 1] = key;          // drop the key into its correct slot
    }
}

Trace on [12, 11, 13, 5, 6]: i=1, key=11 — 12>11 so shift 12 right, insert 11 at index 0 -> [11, 12, 13, 5, 6]. i=2, key=13 — 12<13, no shift needed. i=3, key=5 — shift 13, 12, 11 right, insert 5 at index 0 -> [5, 11, 12, 13, 6]. i=4, key=6 — shift 13, 12, 11 right (5<6, stop), insert 6 -> [5, 6, 11, 12, 13].

Time complexity: O(n²) worst and average case (a reverse-sorted array shifts almost everything on every step). Best case O(n) when the array is already sorted — the inner while loop's condition fails immediately every time, so each element requires only one comparison. Space complexity: O(1).

Why These Are Still Taught

Stability

A sort is stable if two equal elements keep their original relative order after sorting. This matters when sorting objects by one field while wanting ties on that field to preserve an earlier ordering (e.g., sort by score, keeping insertion order among equal scores).

Algorithm	Stable?	Why
Bubble sort	Yes	Only swaps strictly-greater adjacent pairs — equal elements are never swapped past each other.
Selection sort	No	Swapping the minimum into position can jump it past equal elements, changing their relative order.
Insertion sort	Yes	Only shifts strictly-greater elements out of the way — equal elements never move past each other.