Bubble, selection and insertion sort

Why learn sorts you will never ship

Fair question. std::sort exists. Three reasons.

1. They are the smallest complete algorithms you can fully analyse. If you

cannot derive n(n-1)/2 for bubble sort, you will not manage merge sort's recurrence.

1. Insertion sort is actually used - inside std::sort, for sub-arrays

under about 16 elements, where its low constant beats quicksort's overhead.

1. They are guaranteed exam and interview questions. "Which sort is stable?"

is asked constantly.

Bubble sort

Compare neighbours, swap if out of order, repeat. Large values "bubble" to the end.

#include <iostream>
using namespace std;

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;      // already sorted, stop early
    }
}

int main() {
    int a[] = {5, 1, 4, 2, 8};
    bubble_sort(a, 5);
    for (int i = 0; i < 5; i++) cout << a[i] << " ";
    cout << "\n";                 // 1 2 4 5 8
    return 0;
}

Two details carry marks.

The inner loop's - i matters: after pass i, the last i elements are already in final position, so re-checking them is wasted work.

The swapped flag makes the best case O(n). On an already-sorted array the first pass does n-1 comparisons, finds nothing to swap, and stops. Without the flag, bubble sort is O(n^2) even on sorted input, and an examiner will ask about this exact line.

Comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2. That is O(n^2).

Selection sort

Find the smallest remaining element, swap it into place, repeat.

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min_idx]) min_idx = j;
        if (min_idx != i) {
            int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
        }
    }
}

Its one distinguishing property: it performs at most n-1 swaps, the fewest of any comparison sort. Comparisons are still n(n-1)/2 always, best case included - there is no early exit possible, because you cannot know the minimum without looking at everything.

That makes it the choice when a write is far more expensive than a read - flash memory, for example, which wears out on writes.

Insertion sort

Take each element and slide it left into its correct place among the already-sorted part. Exactly how you sort a hand of playing cards.

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];      // shift right
            j--;
        }
        a[j + 1] = key;
    }
}

The j >= 0 must come first in the condition. C++ evaluates && left to right and stops early, so when j reaches -1 the a[j] is never evaluated. Swap the two conditions and you read a[-1], which is undefined behaviour.

Insertion sort's best case is genuinely O(n): on sorted input the while never runs. On nearly-sorted data it is the fastest simple sort by a wide margin, and that is why real libraries use it for small or nearly-ordered ranges.

The comparison table

Stable means equal elements keep their original relative order. Adaptive means it goes faster on partly-sorted input.

The numbers that make the point

Sorting 100,000 elements:

At n = 20, insertion sort wins because merge sort's recursion and temporary array cost more than 400 comparisons. The crossover is somewhere between 10 and 50 elements, which is exactly where library implementations switch.