Sorting algorithms: bubble, selection, insertion sort

If you are in Year 3 of the liceo scientifico (Italian science-focused high school), applied sciences option, and in October in computer science you have finished (or are finishing) loops and arrays, sorting algorithms are the next step: they usually arrive between October and November, and the test that covers them falls six to nine weeks away. There is time to really understand them, instead of learning them by heart. If you are missing the basics on arrays, start from loops and arrays; for the cost of algorithms in general there is complexity and big-O notation, here I only touch on it intuitively.

The idea in one line each

We have to sort an array in increasing order. Three strategies, all based on comparisons and swaps:

• Bubble sort: compares adjacent pairs and swaps them if they are in the wrong order. On each pass the largest value “rises” to the end, like a bubble.
• Selection sort: on each pass it looks for the minimum of the part not yet sorted and moves it to the first free position.
• Insertion sort: keeps the left part sorted and inserts, one at a time, the next element in the right place, like when you sort the cards in your hand.

A trace on an array of 6 elements

We will always use $[5,2,4,6,1,3]$. Hand traces are what you are asked for in a test, so read them with a pencil in your hand.

Bubble sort

Pass 1 (5 comparisons): $(5,2)$ swap → $[2,5,4,6,1,3]$; $(5,4)$ swap → $[2,4,5,6,1,3]$; $(5,6)$ no; $(6,1)$ swap → $[2,4,5,1,6,3]$; $(6,3)$ swap → $[2,4,5,1,3,6]$. The 6 is in its final place.

Pass 2 (4 comparisons): $(2,4)$ no; $(4,5)$ no; $(5,1)$ swap; $(5,3)$ swap → $[2,4,1,3,5,6]$.

Pass 3 (3 comparisons): $(2,4)$ no; $(4,1)$ swap; $(4,3)$ swap → $[2,1,3,4,5,6]$.

Pass 4 (2 comparisons): $(2,1)$ swap → $[1,2,3,4,5,6]$; $(2,3)$ no.

Pass 5 (1 comparison): $(1,2)$ no. Total: 15 comparisons and 9 swaps.

Selection sort

• $i=0$: the minimum of the whole array is 1 (position 4); swap with the 5 → $[1,2,4,6,5,3]$.
• $i=1$: the minimum of $[2,4,6,5,3]$ is 2, already in place; no swap.
• $i=2$: the minimum of $[4,6,5,3]$ is 3; swap with the 4 → $[1,2,3,6,5,4]$.
• $i=3$: the minimum of $[6,5,4]$ is 4; swap with the 6 → $[1,2,3,4,5,6]$.
• $i=4$: the minimum of $[5,6]$ is 5, already in place.

Total: 15 comparisons and 3 swaps (at most $n-1=5$).

Insertion sort

Here elements are “shifted” to the right to make room, then the key $k$ is inserted.

• $k=2$: the 5 is larger, it shifts → $[2,5,4,6,1,3]$ (1 shift).
• $k=4$: the 5 shifts, the 2 does not → $[2,4,5,6,1,3]$ (1).
• $k=6$: the 5 is not larger than 6, so it stays where it is (0).
• $k=1$: 6, 5, 4, 2 shift, then 1 goes to the front → $[1,2,4,5,6,3]$ (4).
• $k=3$: 6, 5, 4 shift, the 2 does not → $[1,2,3,4,5,6]$ (3).

Total: 12 comparisons and 9 shifts. The 9 is no accident: it coincides with the number of swaps in bubble sort, because both remove the inversions one by one, that is, the pairs in which a larger element comes before a smaller one. In $[5,2,4,6,1,3]$ there are $4+1+2+2=9$.

Pseudocode and Python

Bubble sort, in pseudocode:

for i from 0 to n-2:
    for j from 0 to n-2-i:
        if a[j] > a[j+1]:
            tmp = a[j]
            a[j] = a[j+1]
            a[j+1] = tmp

In Python the swap can be written in one line, but understanding the version with tmp matters in all the other languages:

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]

def insertion_sort(a):
    for i in range(1, len(a)):
        k = a[i]
        j = i - 1
        while j >= 0 and a[j] > k:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = k

When you pass an array to a function that modifies it, remember how parameter passing works: I talk about it in pass by value and by reference.

Why they are O(n²) and which one to choose

All three have two nested loops. The outer loop runs about $n$ times and the inner one, on average, about $n/2$: the comparisons are of the order of

For $n=6$ that makes 15, which is exactly the number we counted. If you double $n$ the comparisons become about four times as many: that is the intuitive meaning of $O(n^2)$.

Which to choose:

In bubble sort you can add a check: if in a pass no swap happens, the array is already sorted and you stop. On an already sorted array it makes only $n-1$ comparisons.

The mistakes I see most

Wrong loop limits. In bubble sort the inner index goes up to $n-2-i$ (in Python range(n-1-i)) because inside the loop a[j+1] is read: with a limit one too high you run off the end of the array. In the same way the outer loop must not reach $n$. In selection sort the inner loop starts from $i+1$, not from $i$, otherwise you compare the element with itself.

Swapping without a temporary variable. Writing a[j] = a[j+1] and straight after a[j+1] = a[j] copies the same value twice and the original value of a[j] is lost.

Confusing selection and bubble. Selection sort first looks for the minimum and then swaps once; bubble swaps during the scan.

Forgetting the shifting in insertion sort. If you don’t save the key $k$ before shifting the elements, you overwrite it.

Three worked exercises

1. The worst case of bubble sort

Count the comparisons and swaps of bubble sort on $[4,3,2,1]$.

Pass 1: $(4,3)$, $(4,2)$, $(4,1)$ are three comparisons and three swaps → $[3,2,1,4]$. Pass 2: $(3,2)$ and $(3,1)$, two swaps → $[2,1,3,4]$. Pass 3: $(2,1)$, one swap → $[1,2,3,4]$. Total: $3+2+1=6$ comparisons and $3+2+1=6$ swaps, that is, all 6 pairs are inversions. With the already sorted array $[1,2,3,4]$ and the early-exit check, on the other hand, 3 comparisons and 0 swaps.

2. How fast the cost grows

How many comparisons are needed to sort 10, 100 and 1000 elements with selection sort? And 2000?

For 2000: $\frac{2000\cdot 1999}{2}=1999000$, about 4 times the 499,500 from before: doubling $n$ makes the cost quadruple. Multiplying $n$ by 10 multiplies the comparisons by about 100.

3. Find the mistake

This bubble sort in a language without multiple assignment has two mistakes. Which ones?

for j from 0 to n-1-i:
    if a[j] > a[j+1]:
        a[j] = a[j+1]
        a[j+1] = a[j]

First mistake: with $j$ up to $n-1-i$, when $i=0$ you reach $j=n-1$ and read a[n], outside the array; the correct limit is $n-2-i$. Second mistake: the swap. With $a=[7,3]$, the first assignment gives $[3,3]$ and the second leaves it as $[3,3]$: the 7 has vanished. You need tmp = a[j] before the first assignment and a[j+1] = tmp at the end.

Test yourself

To train on timed reasoning you can use the practice tests for high school. There is not yet a dedicated practice test for computer science: the questions you find cover maths and physics. A good way to prepare is to redo the three traces without looking, changing the array. More resources are on the computer science page; if you need a hand, I give 1-to-1 online tutoring and you can start with a free introductory call. Close to this topic there is also recursion, which usually follows sorting.