Sorting I: bubble, selection, insertion

Sorting is the most studied problem in computer science: if you sort the data, search drops to O(log n), duplicates come side by side, and the smallest/largest are found immediately. This week there are three simple algorithms. All three are O(n²) and slow on large data, but their logic is intuitive and the exam asks for a pass-by-pass trace. Next week we move on to O(n log n) algorithms.

Golden rules:

1. Bubble: in each pass the largest element “bubbles” to the end.
2. Selection: in each pass the smallest of the remaining part is selected to the front.
3. Insertion: in each pass the next element is inserted into its right place in the sorted part on the left.
4. Watch the definition of “pass”. On this page a pass = one round of the outer loop.

Bubble sort

Compare two neighbouring elements; swap if the left one is larger. During one pass the largest element floats to the very end like a bubble. The next pass doesn’t need to look at the last element.

static void bubbleSort(int[] a) {
    int n = a.length;
    for (int pass = 1; pass < n; pass++) {
        boolean swapped = false;
        for (int j = 0; j < n - pass; 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;   // no swap means the array is sorted
    }
}

On {7, 3, 9, 1, 5}, after each pass:

pass 1: [3, 7, 1, 5, 9]
pass 2: [3, 1, 5, 7, 9]
pass 3: [1, 3, 5, 7, 9]
pass 4: [1, 3, 5, 7, 9]
comps=10 swaps=6 inversions(orig)=6

Inside pass 1, comparison by comparison:

[7, 3, 9, 1, 5]   7 > 3 swap  → [3, 7, 9, 1, 5]
                  7 < 9       → no change
                  9 > 1 swap  → [3, 7, 1, 9, 5]
                  9 > 5 swap  → [3, 7, 1, 5, 9]   9 settled in place

In pass 3 the array became sorted, but since a swap was made in that pass the algorithm can’t know it; pass 4 ends with no swaps and stops.

Inversion: a pair with i < j and a[i] > a[j]. Each adjacent swap fixes exactly one inversion; therefore the number of swaps of bubble sort = the number of inversions.

Selection sort

Scan the remaining part, find the index of the smallest, and swap it with the start of the remaining part. The prefix grows by one in every pass and is in its final state.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

{38, 12, 45, 7, 29, 16}:

pass 1: [7, 12, 45, 38, 29, 16]
pass 2: [7, 12, 45, 38, 29, 16]
pass 3: [7, 12, 16, 38, 29, 45]
pass 4: [7, 12, 16, 29, 38, 45]
pass 5: [7, 12, 16, 29, 38, 45]
comps=15 swaps=3

In passes 2 and 5 the smallest was already in place and no real swap happened (the counter counted only the swaps where min != i). The number of comparisons is independent of the input: always $\frac{n(n-1)}{2}$. It makes 15 comparisons on a sorted array too.

PITFALL · Selection sort can’t stop early. The flag idea from bubble doesn’t work here; to find the minimum you have to scan all of the remaining part. The best case is also O(n²).

Insertion sort

Like arranging the cards in your hand in a card game: you take each new card and insert it in the right place among the sorted cards on the left. The larger cards shift one place to the right.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // shift
            j--;
        }
        a[j + 1] = key;
    }
}

{38, 12, 45, 7, 29, 16}:

pass 1: [12, 38, 45, 7, 29, 16]
pass 2: [12, 38, 45, 7, 29, 16]
pass 3: [7, 12, 38, 45, 29, 16]
pass 4: [7, 12, 29, 38, 45, 16]
pass 5: [7, 12, 16, 29, 38, 45]
comps=12 shifts=9 inversions=9

Inside pass 3 (key = 7):

[12, 38, 45, 7, 29, 16]   key = 7
45 > 7 → shift     [12, 38, 45, 45, 29, 16]
38 > 7 → shift     [12, 38, 38, 45, 29, 16]
12 > 7 → shift     [12, 12, 38, 45, 29, 16]
j = -1, stop       [7, 12, 38, 45, 29, 16]

Insertion sort is adaptive: the more sorted the array, the faster. n − 1 comparisons on a sorted array, $\frac{n(n-1)}{2}$ on a reverse-sorted one:

insertion sorted: comps=5 shifts=0
insertion reverse: comps=15 shifts=15

Recognizing the algorithm from a pass

On the exam, an intermediate state is sometimes given and “which algorithm?” is asked. The same input {4, 2, 6, 1, 3}, after the first pass:

Stability

Elements with equal keys keeping their original order after sorting. When you sort a student list already sorted by name by grade, you want those with the same grade to remain sorted by name; this is possible only with a stable algorithm.

Records with keys 3, 3, 1 (the letters show the original order):

selection [1, 3b, 3a] insertion [1, 3a, 3b] bubble [1, 3a, 3b]

Selection sort does a distant swap: while bringing 1 to the front it throws 3a to the very end and makes it jump past 3b. Bubble and insertion swap only neighbours and only if strictly larger (>), so equal elements don’t pass each other.

Comparison table

Number of comparisons on random arrays (n doubles each time):

n=1000 bubble comps=498275 selection comps=499500 insertion comps=245712
n=2000 bubble comps=1996855 selection comps=1999000 insertion comps=985303
n=4000 bubble comps=7996674 selection comps=7998000 insertion comps=3980580

All grow x4: quadratic. Insertion sort makes half as many comparisons as the others on average, because each element stops in the middle of the sorted part on average.

Common mistakes

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // shift the larger ones right
            j--;
        }
        a[j + 1] = key;        // place into the gap
    }
}

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i];
        a[i] = a[min];
        a[min] = t;
    }
}